Cracking the Coding Interview, 6th Edition, 2.8

Question

Task: Given a circular circular linked list, implement algoirthm, which returns the node at the beginning of the loop.

The answer key gives a more complex solution than what I offer. What happened to mine ?:

public static Node loopDetection(Node n1) { ArrayList<Node> nodeStorage = new ArrayList<Node>(); while (n1.next != null) { nodeStorage.add(n1); if (nodeStorage.contains(n1.next)) { return n1; } else { n1 = n1.next; } } return null; } 

Answer 1

Your solution is O(n^2) time (each contains() in an ArrayList is O(n) and O(n) (to store nodeStorage ), while the “more complex” solution is O(n) time and O(1) .

The book proposes the following solution for those who are interested: O(n) time and O(1) space:

If we move two pointers, one at speed 1 and the other at speed 2, they will end the meeting if the linked list has a loop. What for? Thinking about two cars moving along the highway - the faster the car will always go slower! The hard part here is finding the beginning of the cycle. Imagine, as an analogue, two people racing along a track twice as fast as others. If they start at the same place, when will they follow next time? They will follow at the beginning of the next lap. Now let's assume that Fast Runner had an initial level of k meters per n step circle. When will they follow next time? They will meet to the meters until the beginning of the next round. (Why? Fast Runner would take k + 2 (n - k) steps, including its beginning, and Slow Runner would take n - k steps. Both will be to steps before the start of the cycle.) Now, going back to the problem, when Fast Runner (n2) and Slow Runner (n1) are moving around our circular linked list, n2 will start the cycle when n1 enters. In particular, it will have the beginning k, where k is the number of nodes before the cycle. Since n2 has a head beginning k nodes, n1 and n2 will correspond to k nodes before the start of the loop. So, now we know the following: 1. The head is k nodes from LoopStart (by definition). 2. MeetingPoint for n1 and n2 are k nodes from LoopStart (as shown above). Thus, if we move n1 back to Head and save n2 in MeetingPoint, and move them at the same pace, they will meet on LoopStart.

 LinkedListNode FindBeginning(LinkedListNode head) { LinkedListNode n1 = head; LinkedListNode n2 = head; // Find meeting point 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; } 

Answer 2

There is a solution given by amit. The problem is that you either know it or not, but you won’t be able to figure it out in an interview. Since I never had to find a loop in a linked list, knowing that this was pointless to me, except for transmitting the interview. Therefore, for the interviewer, stating this as an interview question, and waiting for the amir’s response (which is nice because it has linear time and zero extra space), is pretty stupid.

So, your solution is mostly fine, except that you have to use a hash table, and you have to make sure that the hash table hashes links to nodes, not nodes. Let's say you have a node containing the string and the “next” pointer, and the hash function hashes the string and compares the nodes as equal if the lines are equal. In this case, you will find the first node with a repeating line, and not node at the beginning of the loop, if you are not careful.

(the amir solution has a very similar problem in languages ​​where == compares objects, not links. For example, in Swift you have to use === (compares links) rather than == (compares objects)).