Fog Creek Software
Discussion Board




How to remove the loop in the linked list

Goal is to locate the place where the loop is occurring and set that node's next to null.

Keep a third pointer at the head.
Once the first two pointers have met, ie., a loop has been detected, freeze the first pointer, and let the 2nd one start circling around. For each circle that it meets the first pointer again without meeting the 3rd pointer, move the 3rd pointer to the next node. When the firstPtr->next() is equal the 3rd pointer, set firstPtr->next() to null.

R
Sunday, June 22, 2003

But thats O(n^2) algorithm. Try to find O(n) algorithm

Igor
Sunday, August 24, 2003

It's an aha puzzle.

I assume that you have to start traversing the linked list starting from a node (either it is passed to you or you may have to pick a node randomly). Let's call this node as *HEAD*. Store the pointer to head node in a local variable. Now, keep traversing and for each node check if the node->next is same as head, if yes assign null to node->next.


node *pHead = Head; //assuming you get the first node somehow. Else, start from a random node.
node *pNode = pHead;

while (pNode != null)
{
    if (pNode->next == pHead)
      {pNode->next = null; break;}
    pNode = pNode->next;
}

ram
Friday, September 12, 2003

i guess the q'n about looped LL ; NOT circular LL.

in looped LL, you may never visit head more than once.

eg: head->2->3->4-> -2 ->5->3 ->4-> -2 ->5 ->3 ... etc

victim
Monday, September 15, 2003

*  Recent Topics

*  Fog Creek Home