Interview: Remove Loop in a linked list - Java

Question

I was asked this question in an interview: “How to define a cycle in a linked list?”, I solved it, but immediately the interviewer asked me how to delete a cycle in a linked list. I fumbled.

So, can any pointers on how to solve this problem be a pseudo-code or a determination method?

I like Java, so I tagged this question under java.

There is a loop for an instance in this linked list

0--->1---->2---->3---->4---->5---->6 ▲ | | ▼ 11<—-22<—-12<—-9<—-8 

Answer 1

This problem has two parts:

• Detect if there is a loop in the list
• Identify the start of a cycle

Once you know where the cycle begins, it is easy to identify the last item in the list, since it is the item in the list after the start of the cycle, which ends, indicating the start of the cycle. Then it’s trivial to set the next pointer / link of this element to null to fix the list of circular links (and not the circular linked list in which the last elements point to the first), this will be a specific instance of circular lists).

• The Floyd loop detection algorithm, also called the turtle and hare algorithm , as it involves the use of two pointers / links that move at different speeds, is one way to detect the loop. If there is a loop, two pointers (e.g. p1 and p2 ) ultimately point to the same element after a finite number of steps. Interestingly, it can be proved that the element they meet will be the same distance to the start of the cycle (continuing to move forward in the list in the same direction) refers to the head of the list as the beginning of the cycle. That is, if there are k elements in the linear part of the list, two pointers will occur inside a cycle of length m at point mk from the beginning of the cycle or element k to the end of the cycle (of course, this is a cycle, so it does not have an “end” - it's just "start" again). And this gives us the opportunity to find the beginning of the cycle:

• Once the loop has been detected, let p2 remain pointing to the element in which the loop is for the above step, but reset p1 so that it returns to the list header. Now move each pointer one item at a time. Since p2 starts inside the loop, it will continue the loop. After k steps (equal to the distance the beginning of the cycle from the head of the list), p1 and p2 will be assembled again. This will give you a link to the start of the loop.

• Now it’s easy to set p1 (or p2 ) to point to the element that starts the cycle and go through the cycle until p1 returns to the original element. At the moment, p1 refers to the "last" list of elements, and the next pointer can be set to null .

---

Here is some quick and dirty Java code assuming a linked Node list, where a Node has a next link. This can be optimized, but it should give you the basic idea:

 Node slow, fast, start; fast = slow = head; //PART I - Detect if a loop exists while (true) { // fast will always fall off the end of the list if it is linear if (fast == null || fast.next == null) { // no loop return; } else if (fast == slow || fast.next == slow) { // detected a loop break; } else { fast = fast.next.next; // move 2 nodes at at time slow = slow.next; // move 1 node at a time } } //PART II - Identify the node that is the start of the loop fast = head; //reset one of the references to head of list //until both the references are one short of the common element which is the start of the loop while(fast.next != slow.next) { fast = fast.next; slow = slow.next; } start = fast.next; //PART III - Eliminate the loop by setting the 'next' pointer //of the last element to null fast = start; while(fast.next != start) { fast = fast.next; } fast.next = null; //break the loop 

---

This explanation may help why Part II:

Suppose the length of the loop is M, and the length of the rest of the linked list is L. Let me understand what is the position in the loop when t1 / t2 first meet?

Define the first node in the loop position 0, following the links, we have position 1, 2, ..., up to M-1. (when we go in a loop, our current position (walk_length) mod M, right?) Let t1 / t2 first meet at position p, then their transit time (L + k1 * M + p) / v = (L + k2 * M + p) / 2v for some k1

So, it concludes that if t1 starts with p, t2 starts from the head and moves around at the same speed, then the grantee will meet at position 0, the first nodecycle. Q.E.D.

Additional links:

• http://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work
• Explain how running a node loop in a linked circular list works?
• Proof of detecting start of loop in linked list
• Christo answered this question on this page also quotes an explanation from the interview book.

Answer 2

Solution 1 - Courtesy of the Career Cup and the book Cracking the Coding Interview :

 public static LinkedListNode findStartOfLoop(LinkedListNode head) { LinkedListNode n1 = head; LinkedListNode n2 = head; // find meeting point using Tortoise and Hare algorithm // this is just Floyd cycle detection algorithm while (n2.next != null) { n1 = n1.next; n2 = n2.next.next; if (n1 == n2) { break; } } // Error check - there is no meeting point, and therefore no loop if (n2.next == null) { return null; } /* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps /* from the Loop Start. If they move at the same pace, they must * meet at Loop Start. */ n1 = head; while (n1 != n2) { n1 = n1.next; n2 = n2.next; } // Now n2 points to the start of the loop. return n2; } 

An explanation of this solution directly from the book:

If we move two pointers, one with speed 1 and the other with speed 2, they will end the meeting if the linked list has a loop. What for? Think of two cars moving along the track; a faster car will always go slower!

The hard part here is finding the beginning of the cycle. Imagine, as an analogue, two people racing along the highway, one running twice as fast as the others. If they start from the same place, when will they follow next time? They will meet at the beginning of the next lap.

Now let's assume that Fast Runner had an entry level of k meters n step. When will they follow meet? They will meet k meters before the start of the next round. (Why? A runner would take k + 2 (n - k) steps, including its beginning, and a Slow runner would take n - k steps. Both will be to steps before the start of the cycle).

Now, returning to the problem, when Fast Runner (n2) and Slow Runner (n1) moves around our circularly linked list, n2 will have a head start on the loop when n1 enters. In particular, it will have an initial start k, where k is the number of nodes before the cycle. Since n2 has an initial start of k nodes, n1 and n2 will correspond to nodes before the start of the cycle.

So now we know the following:

• A chapter is k nodes from LoopStart (by definition)
• MeetingPoint for n1 and n2 are k nodes from LoopStart (as shown above)

So if we move n1 back to Head and save n2 in MeetingPoint and move them both at the same pace, they will meet in LoopStart

Solution 2 - kindly provided by me :)

 public static LinkedListNode findHeadOfLoop(LinkedListNode head) { int indexer = 0; Map<LinkedListNode, Integer> map = new IdentityHashMap<LinkedListNode, Integer>(); map.put(head, indexer); indexer++; // start walking along the list while putting each node in the HashMap // if we come to a node that is already in the list, // then that node is the start of the cycle LinkedListNode curr = head; while (curr != null) { if (map.containsKey(curr.next)) { curr = curr.next; break; } curr = curr.next; map.put(curr, indexer); indexer++; } return curr; } 

Hope this helps. Christo

Answer 3

This answer is not intended to compete for the answer, but rather to explain a little more about the meeting of the two nodes in the turtle and the hare algorithm.

• Both nodes will eventually enter the loop. As one moves faster (F) than the other (S), (F), it will eventually be slanted (S).

• If the start of the loop is in the list header, (F) should meet (S) back in the list header. This is ONLY because (F) speed is 2X (S); if it were 3X, that would be wrong. This is true because (F) completes one circle when (S) completes half of the circle, so when (S) completes its first circle, (F) completes two circles - and returns at the beginning of the cycle with (S).

• If the beginning of the cycle is not in the list header, then by the time (S) entering the cycle, (F) has the initial beginning (k) of nodes in the cycle. Since (S) the speed is only one node at a time, it will occur (F) at (k) nodes from the beginning of the cycle - as in, (k) more steps to reach the beginning, NOT (k) steps AFTER the start. This would not be true if (S) the speed were not one, and the ratio of speeds was not 2: 1 between (F) and (S).

  3.1. That's where it gets a little hard to explain. We can agree that (F) will continue to grind (S) until they converge (see 1 above), but why are there (k) nodes from the start of the cycle? Consider the following equation, where M is the number of nodes or the distance from the cycle, and k is the beginning of the head (F); the equation is the distance traveled (F) by a given time t on the left in terms of the distance traveled on the right (S):

  d_F (t) = 2 * d_S (t) + k

  So, when (S) enters the cycle and runs 0 distances in the cycle, (F) runs only the distance (k). By the time moment d_S = M - k, d_F = 2M - k. Since we must also use modular mathematics, given that M represents the total distance of one circle in the cycle, POSITION (F) and (S) in any whole M (without remainder) is 0. So, then in terms of POSITION (or differential ), this leaves k (or rather, -k).

  So, finally, (S) and (F) will meet at the position (0 - k) or (k) nodes from the start of the cycle.

• According to [3] above, since (k) represents the initial start (F), and when (F) passed 2X, the distance (S) moved to enter the loop from the head of the list, (k) also represents the distance from the beginning list, which then represents the start of the loop.

This is a bit late, so I hope I have articulated it clearly. Let me know about this and I will try to update my answer.

Answer 4

Using an identification hash map (e.g. IdentityHashMap ) is very easy to solve. However, it uses more space.

Move the list of nodes. For each node encountered, add it to the ID card. If the node already exists in the ID card, then the list has a circular link and the node that was before this conflict is known (either check before moving, or save the "last node") - just set "next" if necessary to break the loop.

After this simple approach there should be a fun exercise: the code remains as an exercise for the reader.

Happy coding.

Answer 5

  0--->1---->2---->3---->4---->5---->6 ▲ | | ▼ 11<—-22<—-12<—-9<—-8 

Insert a dummy node element after each node in the list of links, and before installing, verify that the node next to the next one is dummy or not. If next to the next one is dummy, insert a zero into the next of this node.

  0-->D->1-->D->2-->D->3->D-->4->D-->5->D-->6 ▲ | / ▼ 11<—D<-22<—D<-12<—D<-9<—D<--8 Node(11)->next->next == D Node(11)->next =null