LinkedList cycle detection

Problem Statement

LeetCode-141: Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Approach

This is a very common question and we’ll be using Floyd’s Cycle Detection Algorithm to solve this. The algorithm uses two pointers, commonly referred to as the slow and the fast. Here’s a quick summary of how it works:

1. Initialization: Both pointers start at the beginning of the sequence.
2. Start:
   1. The slow moves one step at a time.
   2. The fast moves two steps at a time.
   3. Cycle Detection:
      1. If there is no cycle, the fast pointer will reach the end of the sequence.
      2. If there is a cycle, at some point, the fast and the slow pointers will meet within the cycle.
3. Finding the Start of the Cycle (if required):
   1. Once a meeting point is detected, the slow pointer is reset to the start of the sequence.
   2. Both pointers then move one step at a time until they meet again. The meeting point will be the start of the cycle.

Implementation

Here is a java implementation of the algorithm:

public boolean hasCycle(ListNode head) {
    // if blank list or a single node
    if(null == head || null == head.next){
        return false;
    }
    // initialize to the start of list
    ListNode fast = head;
    ListNode slow = fast;
    // while there are more nodes to process
    while(null != fast.next){
        // move fast one step forward
        fast = fast.next;
        // if not the end of list
        if(null != fast.next){
            // move fast one step ahead (again)
            // now fast is 2 steps ahead
            fast = fast.next;
            // move slow 1 step ahead
            slow = slow.next;
        }
        // if pointing to same node
        if(slow == fast){
            return true;
        }
    }
    // else i.e. end of list is reached
    // return false
    return false;
}

Complexity Analysis

The algorithm efficiently detects cycles with a time complexity of \(O(n)\).