CODEWITHSUNDEEP
javaalgorithmlinked-listbig-otime-complexity
segue_segway
segue_segway

Reputation: 1518

Cracking the Coding Interview, 6th edition, 2.8

Problem Statement: Given a circular linked list, implement an algoirthm that returns the node at the beginning of the loop.

The answer key gives a more complicated solution than what I propose. What's wrong with 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;
}

Upvotes: 8

Views: 2551

Answers (3)

rajiv.cla
rajiv.cla

Reputation: 366

I had trouble visualizing what was going on with this algorithm. Hopefully this helps someone else.

At time t = k(3), p2 is twice the distance from the head(0) as p1, so for them to get back in line, we need p2 to 'catch up' to p1 and it will take L - k(8) 5 more steps to occur. p2 is travelling at 2x the speed of p1.

At time t = k + (L - k) (8), p2 needs to travel k steps forward to get back to k. If we reset p1 back to the head(0), we know that p1 and p2 will both meet back at k(3, 19 respectively) if p2 is travelling at the same speed as p1.

Linked List graphic

Upvotes: 2

gnasher729
gnasher729

Reputation: 52602

There is the solution given by amit. The problem is that you either know it or you don't, but you won't be able to figure it out in an interview. Since I have never had a need to find a cycle in a linked list, knowing it to me is pointless except for passing interviews. So for an interviewer, stating this as an interview question, and expecting amir's answer (which is nice because it has linear time and zero extra space), is quite stupid.

So your solution is mostly fine, except that you should use a hash table, and you must make sure that the hash table hashes references to nodes and not nodes. Say you have a node containing a string and a "next" pointer, and the hash function hashes the string and compares nodes as equal if the strings are equal. In that case you'd find the first node with a duplicate string, and not the node at the start of the loop, unless you are careful.

(amir's solution has a very similar problem in languages where == compares the objects, and not the references. For example in Swift, you'd have to use === (compares references) and not == (compares objects)).

Upvotes: 1

amit
amit

Reputation: 178491

Your solution isO(n^2) time (each contains() in ArrayList is O(n) time) and O(n) space (for storing nodeStorage), while the "more complicated" solution is O(n) time and O(1) space.

The book offers the following solution, to whomever is interested, which is O(n) time and O(1) space:

If we move two pointers, one with speed 1 and another with speed 2, they will end up meeting if the linked list has a loop. Why? Think about two cars driving on a track—the faster car will always pass the slower one! The tricky part here is finding the start of the loop. Imagine, as an analogy, two people racing around a track, one running twice as fast as the other. If they start off at the same place, when will they next meet? They will next meet at the start of the next lap. Now, let’s suppose Fast Runner had a head start of k meters on an n step lap. When will they next meet? They will meet k meters before the start of the next lap. (Why? Fast Runner would have made k + 2(n - k) steps, including its head start, and Slow Runner would have made n - k steps. Both will be k steps before the start of the loop.) Now, going back to the problem, when Fast Runner (n2) and Slow Runner (n1) are moving around our circular linked list, n2 will have a head start on the loop when n1 enters. Specifically, it will have a head start of k, where k is the number of nodes before the loop. Since n2 has a head start of k nodes, n1 and n2 will meet k nodes before the start of the loop. So, we now know the following: 1. Head is k nodes from LoopStart (by definition). 2. MeetingPoint for n1 and n2 is k nodes from LoopStart (as shown above). Thus, if we move n1 back to Head and keep n2 at MeetingPoint, and move them both at the same pace, they will meet at 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;
   }

Upvotes: 8

Related Questions