[Linked List] Detect Loop

The standard linear time solution for this is as follows:

• Take two pointers fast and slow
• Increment slow pointer by one node (node.next) and fast pointer by two nodes (node.next.next)
• If the two pointers merge at some point before the fast pointer reaches the end (this happens only if there is no loop), then there exists a loop in linked list

For example consider the following linked list:

Dry run for the above example:

Take two pointers Fast and Slow. Initially both of them point to beginning of the linked list.

Here in this example both points to 1. Increment slow pointer by one node (slow.next) and fast pointer by two nodes (fast.next.next). In this process if the linked list contains a loop, both of them meet at some point inside the loop.

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

Here both of them meet at node that contains data as 5. Hence there exists a loop in the linked list.

The naive approach requires O(N^2) time and O(N) space. Basically you store all visited nodes, and compare each of them while traversing each node.

The best solution runs in O(N) time and uses O(1) space. It uses two pointers (one slow pointer and one fast pointer). The slow pointer advances one node at a time, while the fast pointer traverses twice as fast. If the list has loop in it, eventually the fast and slow pointer will meet at the same node. On the other hand, if the loop has no loop, the fast pointer will reach the end of list before the slow pointer does.

   1: /**

   2:  * Definition for singly-linked list.

   3:  * struct ListNode {

   4:  *     int val;

   5:  *     ListNode *next;

   6:  *     ListNode(int x) : val(x), next(NULL) {}

   7:  * };

   8:  */

   9: class Solution {

  10: public:

  11:     bool hasCycle(ListNode *head) {

  12:       ListNode * SlowPtr = head, * FastPtr = head ;

  13:

  14:       while ( SlowPtr && FastPtr && FastPtr->next ) {

  15:           SlowPtr = SlowPtr->next ;

  16:           FastPtr = FastPtr->next->next ;

  17:

  18:           if ( SlowPtr == FastPtr )

  19:             return true ;

  20:       }

  21:       return false ;

  22:     }

  23: };