Interview Questions

How could you determine if a linked list contains a cycle in it, and, at what node the cycle starts?

Microsoft Interview Questions and Answers

(Continued from previous question...)

15. How could you determine if a linked list contains a cycle in it, and, at what node the cycle starts?

Question: How could you determine if a linked list contains a cycle in it, and, at what node the cycle starts?

Answer: There are a number of approaches. The approach I shared is in time N (where N is the number of nodes in your linked list). Assume that the node definition contains a boolean flag, bVisited.

struct Node
{
...
bool bVisited;
};

Then, to determine whether a node has a loop, you could first set this flag to false for all of the nodes:

// Detect cycle
// Note: pHead points to the head of the list (assume already exists)
Node *pCurrent = pHead;
while (pCurrent)
{
pCurrent->bVisited = false;
pCurrent = pCurrent->pNext;
}

Then, to determine whether or not a cycle existed, loop through each node. After visiting a node, set bVisited to true. When you first visit a node, check to see if the node has already been visited (i.e., test bVisited == true). If it has, you've hit the start of the cycle!

bool bCycle = false;
pCurrent = pHead;
while (pCurrent && !pCycle)
{
if (pCurrent->bVisited == true)
// cycle!
pCycle = true;
else
{
pCurrent->bVisited = true;
pCurrent = pCurrent->pNext;
}
}


A much better approach was submitted by 4Guys visitor George R., a Microsoft interviewer/employee. He recommended using the following technique, which is in time O(N) and space O(1).

Use two pointers.
// error checking and checking for NULL at end of list omitted
p1 = p2 = head;

do {
p1 = p1->next;
p2 = p2->next->next;
} while (p1 != p2);

p2 is moving through the list twice as fast as p1. If the list is circular, (i.e. a cycle exists) it will eventually get around to that sluggard, p1.

(Continued on next question...)

Other Interview Questions