techInterview Discussion

A part of answers to technical interview questions.

Your host: Michael Pryor

remove a loop from a linked list

Guys this is the question which follows once you answer the classic question - "detect a loop in a linked list"

any ideas?
Saturday, March 11, 2006
A slow way off the cuff is:

Let N be the node where you first detected the cycle.
p1 = head

for (p1 = head .. N)
  p2 = N
    if p2->next == p1
      p2->next = NIL
      p2 = p2->next
  while (p2 != N)
end for

Pretty ugly.
Anonymous Student
Saturday, March 11, 2006
There is a certain irony in these problems.  For a software person, a linked list should always have a tail.  I suppose there may be hardware problems that could have tailless linked lists, but even that isn't likely (for example, limited entry full directory scheme did use a tail (e.g. the MIT Alewife).
Anonymous Student
Saturday, March 11, 2006
I think this question already appeared here, but here's an O(n) solution anyway.

Start from the node at which you detected the loop and go around the loop until you reach it again.  Count the nodes on the way, so now you have the size of the loop, say, k.  Start two pointers from the head, one lagging k-1 nodes behind the other.  Cut the loop open when the node pointed to by the first pointer points to the node pointed to by the second.
Sunday, March 12, 2006
Let p1, p2 pointers (to node). Traverse p1 by one node and p2 by 2 nodes. At one pt (after one complete cycle by p2) p1 and p2 will point the same node if the loop really exists.

bloopExist = false; 
p1 = start_node;
p2 = start_node;
 p1 = p1->next;
 p2 = p2->next->next;
 if(p1 == p2) then
  bloopExist = true; 

 if(p1==null or p2==null) // reaches the end of list, so no loop.

}while (true);

Thanks <>
Satheesh Send private email
Friday, March 24, 2006

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz