How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list.

Originally thread from:
http://vijayinterviewquestions.blogspot.com/2007/05/how-would-you-detect-loop-in-linked.html

This is also one of the classic interview questions
There are multiple answers to this problem. Here are a few C programs to attack this problem.


Brute force method
Have a double loop, where you check the node pointed to by the outer loop, with every node of the inner loop.

typedef struct node

{

void *data;

struct node *next;

}mynode;


mynode * find_loop(NODE * head)

{

mynode *current = head;

while(current->next != NULL)

{

mynode *temp = head;

while(temp->next != NULL && temp != current)

{

if(current->next == temp)

{

printf("\nFound a loop.");

return current;

}

temp = temp->next;

}

current = current->next;

}

return NULL;

}


Visited flag
Have a visited flag in each node of the linked list. Flag it as visited when you reach the node. When you reach a node and the flag is already flagged as visited, then you know there is a loop in the linked list.

Fastest method
Have 2 pointers to start of the linked list. Increment one pointer by 1 node and the other by 2 nodes. If there's a loop, the 2nd pointer will meet the 1st pointer somewhere. If it does, then you know there's one.

Here is some code
p=head;

q=head->next;
while(p!=NULL && q!=NULL)

{

if(p==q) { //Loop detected! exit(0); }

p=p->next;

q=(q->next)?(q->next->next):q->next;

}
// No loop.

Finding Missing Number in C#

static int findmissingnum(int[] num) //1 2 3 5
{
if (num == null) throw new ArgumentNullException("num");
if (num.Length == 0) throw new ArgumentOutOfRangeException("num");

if (num[num.Length - 1] == num.Length)
return 0;

int startIndex = 0;
int endIndex = num.Length - 1;
int midNumber = num.Length / 2;

while (midNumber >= startIndex && midNumber <= endIndex)
{
if (num[midNumber] == midNumber + 1)
{
if (startIndex == midNumber)
{
break;
}
startIndex = midNumber;
midNumber = (midNumber + num.Length - 1) / 2;
}
else
{
if (startIndex == midNumber)
{
midNumber--; break;
}

endIndex = midNumber;
midNumber = (midNumber + startIndex) / 2;
}
}
if (midNumber == -1)
return 1;

return num[midNumber] + 1;
}

Test Cases:
1. null
2. zero length int []
3. first numer is missing 2,3,4,5
1,2,4,5
1,3,4,5
1,2,3,5
1 and 1,2 and 1,2,3 and 1,2,3,4and 1,2,3,4,5 and 1,2,3,4,5,6

1,2,4,5
1,3,4,5
1,2,3,5
1 and 1,2 and 1,2,3 and 1,2,3,4and 1,2,3,4,5 and 1,2,3,4,5,6
if (num[num.Length - 1] == num.Length)
return 0;
1 1,2 1,2,3 1,2,3,4
thead safe
int[] num
1M
int32.MaxValue
2^31
2^31-1
stable
environment
doc