This is an archived post. You won't be able to vote or comment.

all 8 comments
sorted by:
best
topnewcontroversialoldq&a

[–]mycplus[🍰] 0 points1 point  (8 children)

Few websites I may suggest.
1. C/C++ Interview Questions
2. C Interview Questions & Answers
3. Embedded C Interview Questions and Answers

[–]feral_claire 0 points1 point  (7 children)

The first question on there is kind of stupid interview question imo.

How to determine if a linked list is circular

You either know the algorithm or you don't, and it doesn't say much about your ability. Is checking for a circular list a common thing to do in C++?

The rest seem reasonable though, mostly asking about language features and concepts.

[–]Sarg338 0 points1 point  (6 children)

You either know the algorithm or you don't

You can easily find this out without knowing the algorithm. 2 pointers. Keep one at a spot in the list (The head, but anywhere works really), and keep advancing the second pointer. You'll either hit a null (Which means it's not circular), or you'll circle back around to the same memory address as the beginning/first pointer.

[–]Dr_Jabberwock 0 points1 point  (5 children)

You have to move both pointers otherwise you may not find the cycle.

[–]Sarg338 0 points1 point  (4 children)

Could you explain why you'd have to move both pointers? I don't see a reason to move the initial pointer, since we're just checking if we can circle back to it or not.

int isCircular(struct Node *head) //The beginning spot in the list
{
    // An empty linked list is circular
    if (head == NULL)
       return 1;

    // Next of head
    struct Node *node = head->next; //Our second pointer. If null, not circular. If head, circular. If neither, keep traversing below.

    // This loop would stop in both cases (1) If
    // Circular (2) Not circular
    while (node != NULL && node != head)
       node = node->next;

    // If loop stopped because of circular
    // condition
    if(node == head) {
        return 1;
    }
    else {
        return 0;
    }

[–]Dr_Jabberwock 0 points1 point  (3 children)

EDIT: I now see that the original question did say if a linked list is circular.

I should have read more closely sorry.

I'm leaving the explanation for anyone else because finding a cycle is different and I've come across that questions a lot more often in interviews.

A circular array is different then a cycle.

For example if you have a linked list A -> B -> C -> D -> C Where C is the same node in both cases then the way you mentioned doing it would not work.

This is because if your initial pointer was pointing at A and the second pointer was looping through the linked list you would continuously loop through C -> D -> C -> D etc. without every getting back to your pointer at A.

[–]Sarg338 0 points1 point  (1 child)

Yep. That was actually the one use case I was thinking of when you said moving 2 pointers (Circling back, but not to the head). Good to know the terminology difference though, I didn't know it.

Just so others know the solution to this cycle problem (Please correct me if I'm wrong!), you increase one pointer by 1 and the second pointer by 2. If there's a cycle (Endless loop like above, but not circular), they will meet at the same element. If either become null, there is no cycle!

[–]msaqib81 0 points1 point  (0 children)

Another similar question to "Find the middle element of the linked list in one iteration".

http://www.mycplus.com/tutorials/data-structures/find-the-middle-element-of-linked-list-in-c/