Problem Description

The "Linked List Cycle II" problem asks you to detect if a given singly linked list contains a cycle. If a cycle exists, you must return the node where the cycle begins. If there is no cycle, return null.

• You are given the head of a singly linked list.
• There is at most one cycle in the list.
• You must not modify the linked list or reuse elements.
• Your solution should use constant extra space if possible.

For example, given a list: 3 → 2 → 0 → -4 where -4 points back to 2, you should return the node with value 2.

Thought Process

At first glance, the problem seems to require traversing the list and checking if any node is visited more than once. One way is to use a data structure (like a hash set) to record visited nodes. If we encounter the same node again, we have found the start of the cycle.

However, the problem asks for an optimized solution with constant space. This leads us to consider the classic "Floyd’s Tortoise and Hare" algorithm, which uses two pointers moving at different speeds to detect cycles without extra space.

The challenge is not only to detect the cycle but also to find the node where the cycle begins. This requires a deeper understanding of how pointers interact as they traverse the list.

Solution Approach

We use Floyd's Tortoise and Hare algorithm, which consists of two main phases:

1. Detect if a cycle exists:
   • Initialize two pointers, slow and fast, both at head.
   • Move slow one step at a time, and fast two steps at a time.
   • If fast or fast.next becomes null, there is no cycle.
   • If slow and fast meet, a cycle exists.
2. Find the entry point of the cycle:
   • Reset slow to head, keep fast at the meeting point.
   • Move both pointers one step at a time.
   • The node where they meet is the start of the cycle.

Why does this work? The distance from head to the cycle start equals the distance from the meeting point to the cycle start (when moving at the same speed).

This approach uses only two pointers and no extra memory, achieving O(1) space and O(n) time.

Example Walkthrough

Suppose we have a linked list: 3 → 2 → 0 → -4, with -4 pointing back to 2.

1. Detect cycle:
   • slow at 3, fast at 3
   • Move: slow at 2, fast at 0
   • Move: slow at 0, fast at 2
   • Move: slow at -4, fast at -4 (they meet!)
2. Find cycle start:
   • Reset slow to head (3), fast stays at -4
   • Move: slow at 2, fast at 2 (they meet!)
3. The cycle begins at the node with value 2.

Time and Space Complexity

• Brute-force (using a hash set):
  • Time Complexity: O(n), as we may visit each node once.
  • Space Complexity: O(n), since we may store each node in a set.
• Optimized (Floyd's algorithm):
  • Time Complexity: O(n), since both pointers traverse at most 2n steps.
  • Space Complexity: O(1), as only pointers are used.

The optimized approach is preferred for its constant space usage and linear time.

Summary

To solve the Linked List Cycle II problem, we use Floyd's Tortoise and Hare algorithm. This elegant approach detects cycles using two pointers and then cleverly locates the cycle's start by exploiting pointer movement properties. The solution is optimal, requiring only constant space and linear time, and highlights the power of pointer manipulation in linked list problems.

Code Implementation

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        # Phase 1: Detect if a cycle exists
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        else:
            return None
        # Phase 2: Find the entry point
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow
      

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        // Phase 1: Detect if a cycle exists
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                break;
        }
        if (!fast || !fast->next)
            return nullptr;
        // Phase 2: Find the entry point
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};
      

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // Phase 1: Detect if a cycle exists
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast)
                break;
        }
        if (fast == null || fast.next == null)
            return null;
        // Phase 2: Find the entry point
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

var detectCycle = function(head) {
    let slow = head;
    let fast = head;
    // Phase 1: Detect if a cycle exists
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) break;
    }
    if (!fast || !fast.next) return null;
    // Phase 2: Find the entry point
    slow = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
};