Linked List Cycle

LeetCode 141: Linked List Cycle Solution & Explanation

Problem Overview

TL;DR: To solve this problem efficiently, we utilize the "Fast and Slow Pointers" technique (Floyd's Cycle-Finding Algorithm) to traverse the list at different speeds, guaranteeing a collision if a cycle exists.

The Linked List Cycle problem asks us to determine if a singly linked list contains a loop. A cycle occurs if a node’s next pointer eventually points back to a previous node in the sequence, causing a traversal to continue indefinitely. We are given the head of the list and must return true if a cycle exists and false otherwise. This is a fundamental LeetCode 141 problem often used to test understanding of pointer manipulation and memory constraints.

Brute Force Approach for Linked List Cycle

The most intuitive way to detect a cycle is to keep a record of every node we have visited. As we traverse the linked list, we check if the current node has already been encountered.

1. Initialize a Hash Set to store node references (memory addresses).
2. Traverse the linked list starting from the head.
3. For every node, check if it exists in the Hash Set.
   • If yes, a cycle is detected. Return true.
   • If no, add the node to the Hash Set and move to the next node.
4. If the traversal reaches null (the end of the list), return false.

Pseudo-code:

function hasCycle(head):
    seen_nodes = Set()
    current = head
    while current is not null:
        if current in seen_nodes:
            return true
        seen_nodes.add(current)
        current = current.next
    return false

Complexity Analysis:

• Time Complexity: $O(N)$, where $N$ is the number of nodes. We visit each node once.
• Space Complexity: $O(N)$. We must store a reference to every node in the set.

Why this approach is suboptimal: While correct, the brute force approach requires $O(N)$ memory. In systems with limited memory or strictly constrained environments (like embedded systems or the follow-up requirement of this problem), allocating linear space is inefficient. We need a solution that uses constant $O(1)$ memory.

Algorithm Strategy: Two Pointer Patterns

1. Initialization: Initialize two pointers, slow and fast, both pointing to the head of the linked list.
2. Traversal: Enter a loop that continues as long as fast and fast.next are not null. This prevents runtime errors when accessing next pointers.
3. Step Updates: In each iteration:
   • Move slow forward by one node (slow = slow.next).
   • Move fast forward by two nodes (fast = fast.next.next).
4. Collision Check: Immediately after moving, check if slow and fast point to the same object in memory.
   • If slow == fast, a cycle exists. Return true.
5. Termination: If the loop exits (meaning fast or fast.next became null), the list ends. Return false.

Execution Flow

1. Edge Case Check: If head is null, return false immediately.
2. Pointer Setup: Set slow = head and fast = head.
3. Iteration 1:
   • Check: Is fast valid and fast.next valid? Yes.
   • Update: slow moves 1 step. fast moves 2 steps.
   • Compare: Are they equal? No.
4. Iteration 2:
   • Check: Is fast valid and fast.next valid? Yes.
   • Update: slow moves 1 step. fast moves 2 steps.
   • Compare: Are they equal? No.
5. ... Iteration N:
   • Pointers continue moving. If a cycle exists, fast enters the cycle, followed by slow.
   • Once both are in the cycle, the distance between them $k$ decreases by $1$ in every step ($k, k-1, k-2, ..., 0$).
   • Eventually, slow == fast. Return true.
6. Exit: If fast reaches null, return false.

Proof of Correctness

The correctness relies on modular arithmetic within the cycle. Let the cycle length be $L$. When both pointers are in the cycle, let the distance from slow to fast (moving forward) be $k$.

• In one step, slow moves $+1$ and fast moves $+2$.
• The distance between them changes by $(2 - 1) = 1$ unit.
• Specifically, the distance reduces from $k$ to $k-1$.
• Since the distance decreases by exactly 1 per step, it must eventually reach 0. It is impossible for fast to skip over slow.
• If there is no cycle, the linear structure ensures fast reaches null in $O(N/2)$ steps.

Pattern Reuse Notes

The Two Pointers - Fast & Slow pattern is a versatile technique used in several other LeetCode problems:

• LeetCode 202: Happy Number: This problem can be modeled as a cycle detection problem where the sequence of numbers generated by the sum of squares forms a linked list structure.
• LeetCode 287: Find the Duplicate Number: This is an advanced application of Floyd's Cycle Detection on an array, treating indices and values as pointers.
• LeetCode 392: Is Subsequence: While this primarily uses the standard Two Pointer approach (one for each string), it shares the fundamental concept of traversing linear data structures with independent pointers to validate a condition.

Reference Implementation

C++ Solution for LeetCode 141

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 */
9class Solution {
10public:
11    bool hasCycle(ListNode *head) {
12        if (!head) return false;
13
14        ListNode *slow = head;
15        ListNode *fast = head;
16
17        while (fast != nullptr && fast->next != nullptr) {
18            slow = slow->next;          // Move slow pointer by 1
19            fast = fast->next->next;    // Move fast pointer by 2
20
21            if (slow == fast) {         // Collision detected
22                return true;
23            }
24        }
25
26        return false; // Fast reached null, so no cycle
27    }
28};

Java Solution for LeetCode 141

1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode(int x) {
7 *         val = x;
8 *         next = null;
9 *     }
10 * }
11 */
12public class Solution {
13    public boolean hasCycle(ListNode head) {
14        if (head == null) return false;
15
16        ListNode slow = head;
17        ListNode fast = head;
18
19        while (fast != null && fast.next != null) {
20            slow = slow.next;           // Move slow pointer by 1
21            fast = fast.next.next;      // Move fast pointer by 2
22
23            if (slow == fast) {         // Collision detected
24                return true;
25            }
26        }
27
28        return false; // Fast reached null, so no cycle
29    }
30}

Python Solution for LeetCode 141

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, x):
4#         self.val = x
5#         self.next = None
6
7class Solution:
8    def hasCycle(self, head: Optional[ListNode]) -> bool:
9        if not head:
10            return False
11        
12        slow = head
13        fast = head
14        
15        while fast and fast.next:
16            slow = slow.next        # Move slow pointer by 1
17            fast = fast.next.next   # Move fast pointer by 2
18            
19            if slow == fast:        # Collision detected
20                return True
21                
22        return False # Fast reached None, so no cycle