Linked List Cycle II – 142. LeetCode

The Linked List Cycle II problem asks you to determine where a cycle begins in a linked list if one exists. A cycle occurs when a node in the list points back to a previous node, creating a loop. The task involves returning the starting node of the cycle or null if no cycle exists.

This problem is commonly encountered in scenarios involving data structures where circular references might occur, and detecting these cycles is crucial for preventing infinite loops or memory issues.

Brute Force Approach

Approach

Using a hash set to track visited nodes is a straightforward way to detect cycles. Traverse the list, storing each node in the set, and return the first node that is revisited.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode current = head;

        while (current != null) {
            if (visited.contains(current)) {
                return current; // Cycle detected
            }
            visited.add(current);
            current = current.next;
        }
        return null; // No cycle
    }
}

1. Use a HashSet to track nodes as you traverse the list.

2. If a node is revisited (exists in the set), return that node as the start of the cycle.

3. If the traversal ends (current == null), there is no cycle.

Optimal Approach

Algorithm and Data Structure

The optimal approach uses Floyd’s Tortoise and Hare Algorithm (two-pointer technique), achieving  O(1)  space complexity.

• Use two pointers:

• A slow pointer (slow) moves one step at a time.

• A fast pointer (fast) moves two steps at a time.

• If there is a cycle, the two pointers will meet inside the loop.

• After detecting a cycle, move one pointer back to the head and keep the other at the meeting point. Move both one step at a time. They will meet at the start of the cycle.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode slow = head, fast = head;

        // Step 1: Detect if a cycle exists
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                // Step 2: Find the cycle's start
                ListNode pointer = head;
                while (pointer != slow) {
                    pointer = pointer.next;
                    slow = slow.next;
                }
                return pointer; // Start of cycle
            }
        }
        return null; // No cycle
    }
}

Line-By-Line Explanation

Step 1: Base Case:

if (head == null || head.next == null) return null;

• Handles edge cases where the list is empty or only has one node.

Step 2: Initialize Pointers

ListNode slow = head, fast = head;

• slow and fast pointers start at the head of the list

Step 3: Cycle Detection

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;

• slow moves one step, and fast moves two steps
• If fast reaches the end, there is no cycle

Step 4: Meeting Point

if (slow == fast) {

• If slow and fast meet, a cycle is detected.

Step 5: Finding the Start of the Cycle

ListNode pointer = head;
while (pointer != slow) {
    pointer = pointer.next;
    slow = slow.next;
}

• Reser pointer to the head.
• Both pointer and slow move one step at a time until they meet. The meeting point is the start of the cycle.

Step 6: Return

return pointer;

• Return the node where the cycle begins.

Why This Code Works

1. Space Complexity:  O(1) 

• Only two pointers are used, avoiding extra memory for storing visited nodes.

2. Time Complexity:  O(n) 

• Each pointer traverses the list at most twice.

3. Elegant and Efficient:

• The two-pointer technique is a widely recognized algorithmic pattern for detecting cycles.