142. Linked List Cycle II

Problem Description

The problem presents a linked list and asks us to determine where a cycle begins within it. A cycle in a linked list happens when a node's next reference points back to a previous node in the list, causing a portion of the list to be traversed endlessly. We are given the head of the linked list, and we must find the node at which this cycle starts. If there is no cycle, our function should return null.

A linked list cycle is conceptually akin to a running track, where the entry point of the cycle is the "gate" to the track, and the cycle itself is the loop. Our goal is to figure out where this "gate" is located within the list.

Intuition

To resolve the problem of finding out the cycle’s starting point, we can use the two-pointer technique, which is efficient and doesn't require extra memory for storage.

The intuition behind this algorithm involves a faster runner (the fast pointer) and a slower runner (the slow pointer), both starting at the head of the linked list. The fast pointer moves two steps at a time while the slow pointer moves only one. If a cycle exists, the fast pointer will eventually lap the slow pointer within the cycle, indicating that a cycle is present.

Once they meet, we can find the start of the cycle. To do this, we set up another pointer, called ans, at the head of the list and move it at the same pace as the slow pointer. The place where ans and the slow pointer meet again will be the starting node of the cycle.

Why does this work? If we consider that the distance from the list head to the cycle entrance is x, and the distance from the entrance to the meeting point is y, with the remaining distance back to the entrance being z, we can make an equation. Since the fast pointer travels the distance of x + y + n * (y + z) (where n is the number of laps made) and slow travels x + y, and fast is twice as fast as slow, then we can deduce that x = n * (y + z) - y, which simplifies to x = (n - 1) * (y + z) + z. This shows that starting a pointer at the head (x distance to the entrance) and one at the meeting point (z distance to the entrance) and moving them at the same speed will cause them to meet exactly at the entrance of the cycle.

Learn more about Linked List and Two Pointers patterns.

Solution Approach

In this solution, we use the two-pointer technique, which involves having two iterators moving through the linked list at different speeds: slow and fast. slow moves one node at a time, while fast moves two nodes at a time.

The algorithm is divided into two main phases:

Detecting the cycle: Initially, both slow and fast are set to start at the head of the list. We then enter a loop in which fast advances two nodes and slow advances one node at a time. If there is no cycle, the fast pointer will eventually reach the end of the list and we can return null at this point, as there is no cycle to find the entrance of.

However, if there is a cycle, fast is guaranteed to meet slow at some point within the cycle. The meeting point is not necessarily the entrance to the cycle, but it indicates that a cycle does exist.
Finding the cycle starting node: When fast and slow meet, we introduce a new pointer called ans and set it to the head of the list. Now, we move both ans and slow one node at a time. The node at which they conjoin is the start of the cycle.

Why does the above approach lead us to the start of the cycle? We derive this from the fact that:

The distance from the list's head to the cycle's entrance is denoted as x.
The distance from the cycle's entrance to the first meeting point is y.
The remaining distance from the meeting point back to the entrance is z.

Using these variables, we know that when fast and slow meet, fast has traveled x + y + n * (y + z) which is the distance to the meeting point plus n laps of the cycle.

Since fast travels at twice the speed of slow, the distance slow has traveled (x + y) is half that of fast, leading us to the equation 2(x + y) = x + y + n * (y + z). Simplifying this, we find x = (n - 1)(y + z) + z.

This equation essentially states that the distance from the head to the cycle entrance (x) is equal to the distance from the meeting point to the entrance (z) plus some multiple of the cycle's perimeter (y + z). This is why moving the ans pointer from the head and slow from the meeting point at the same pace will lead them to meet at the cycle's entrance.

The Python code provided implements this approach efficiently, using only two extra pointers (fast and slow) for detection and one extra (ans) for locating the cycle's entrance.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple linked list example to walk through the solution approach:

Suppose we have the linked list 1 -> 2 -> 3 -> 4 -> 5 -> 2 (the last node points back to the second one, creating a cycle). Here, the node with the value 2 is the start of the cycle.

Detecting the cycle:
- Initially, both slow and fast pointers are at the head of the list (node with value 1).
- Move slow to the next node (2) and fast two nodes forward (3).
- Move slow to the next node (3) and fast two nodes forward (5).
- Continue this process until fast and slow meet. In our case, after few iterations, fast and slow both point to one of the nodes inside the cycle (let's say they meet at node with value 4).
Finding the cycle starting node:
- Place the ans pointer at the head of the list (node with value 1).
- Move ans to the next node (2) and slow to the next node (5).
- Continue moving both ans and slow one node at a time. As the pointers move one step each turn, they will meet at the node that is the start of the cycle.
- In our case, ans and slow will both meet at the node with value 2, which is the correct entrance to the cycle.

By following these steps and the reasonings behind the solution approach, we are able to find that the node with the value 2 is the entry point of the cycle in the linked list without using any extra memory for storage, only the two pointer variables fast, slow, and later the ans pointer.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, value=0, next=None):
4        self.value = value
5        self.next = next
6
7class Solution:
8    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
9        # Initialize two pointers, slow and fast
10        slow = fast = head
11
12        # Traverse the linked list with two pointers moving at different speeds
13        while fast and fast.next:
14            slow = slow.next  # Slow pointer moves one step
15            fast = fast.next.next  # Fast pointer moves two steps
16          
17            # Check if the slow and fast pointers meet, indicating a cycle
18            if slow == fast:
19                # Initialize another pointer to the head of the linked list
20                start = head
21              
22                # Move both pointers at the same speed until they meet at the cycle's start node
23                while start != slow:
24                    start = start.next
25                    slow = slow.next
26              
27                # Return the node where the cycle begins
28                return start
29      
30        # If no cycle is detected, return None
31        return None
32

1// Definition for singly-linked list.
2class ListNode {
3    int val;
4    ListNode next;
5
6    ListNode(int x) {
7        val = x;
8        next = null;
9    }
10}
11
12public class Solution {
13    // This method detects the node where the cycle begins in a linked list
14    public ListNode detectCycle(ListNode head) {
15        // Two pointers initialized to the start of the list
16        ListNode fast = head;
17        ListNode slow = head;
18
19        // Loop until the fast pointer reaches the end of the list
20        while (fast != null && fast.next != null) {
21            // Move the slow pointer by one step
22            slow = slow.next;
23            // Move the fast pointer by two steps
24            fast = fast.next.next;
25            // If they meet, a cycle is detected
26            if (slow == fast) {
27                // Initialize another pointer to the start of the list
28                ListNode start = head;
29                // Move both pointers at the same pace
30                while (start != slow) {
31                    // Move each pointer by one step
32                    start = start.next;
33                    slow = slow.next;
34                }
35                // When they meet again, it's the start of the cycle
36                return start;
37            }
38        }
39        // If we reach here, no cycle was detected
40        return null;
41    }
42}
43

1// Definition for singly-linked list.
2struct ListNode {
3    int val;
4    ListNode *next;
5    ListNode(int x) : val(x), next(nullptr) {}
6};
7
8class Solution {
9public:
10    // This function detects a cycle in a linked list and returns the node
11    // where the cycle begins. If there is no cycle, it returns nullptr.
12    ListNode* detectCycle(ListNode* head) {
13        ListNode* fastPointer = head; // Fast pointer will move two steps at a time
14        ListNode* slowPointer = head; // Slow pointer will move one step at a time
15
16        // Loop until the fast pointer reaches the end of the list, 
17        // or until the fast and slow pointers meet, indicating a cycle.
18        while (fastPointer && fastPointer->next) {
19            slowPointer = slowPointer->next;            // Move slow pointer one step
20            fastPointer = fastPointer->next->next;      // Move fast pointer two steps
21
22            // Check if the slow and fast pointers have met, indicating a cycle.
23            if (slowPointer == fastPointer) {
24                ListNode* entryPoint = head; // Start from the head
25
26                // Loop until the entry point of the cycle is found.
27                while (entryPoint != slowPointer) {
28                    entryPoint = entryPoint->next;       // Move entry point one step
29                    slowPointer = slowPointer->next;     // Move slow pointer one step
30                }
31
32                // The entry point is where the slow pointer and entry point meet.
33                return entryPoint;
34            }
35        }
36
37        // If the loop exits without the pointers meeting, there is no cycle.
38        return nullptr;
39    }
40};
41

1// Definition for singly-linked list node.
2interface ListNode {
3    val: number;
4    next: ListNode | null;
5}
6
7/**
8 * Detects a cycle in a linked list and returns the node where the cycle begins.
9 * If there is no cycle, it returns null.
10 * @param head - The head of the singly-linked list.
11 * @returns The node where the cycle begins or null if no cycle exists.
12 */
13function detectCycle(head: ListNode | null): ListNode | null {
14    // Initialize two pointers, slow and fast.
15    let slow: ListNode | null = head;
16    let fast: ListNode | null = head;
17
18    // Traverse the list with two pointers moving at different speeds.
19    while (fast !== null && fast.next !== null) {
20        slow = slow!.next; // Move slow pointer one step.
21        fast = fast.next.next; // Move fast pointer two steps.
22
23        // If slow and fast pointers meet, a cycle exists.
24        if (slow === fast) {
25            // Initialize another pointer to the beginning of the list.
26            let startPoint: ListNode | null = head;
27            // Move the startPoint and slow pointer at the same speed.
28            while (startPoint !== slow) {
29                startPoint = startPoint!.next;
30                slow = slow!.next;
31            }
32            // The node where both pointers meet is the start of the cycle.
33            return startPoint;
34        }
35    }
36
37    // If no cycle is detected, return null.
38    return null;
39}
40

Time and Space Complexity

The time complexity of the code is O(n), where n is the number of nodes in the linked list. This is because in the worst case, both fast and slow pointers traverse the entire list to detect a cycle, and then a second pass is made from the head to the point of intersection which is also linear in time.

The space complexity of the code is O(1). This is due to the fact that no additional space proportional to the size of the input linked list is being allocated; only a fixed number of pointer variables fast, slow, and ans are used, irrespective of the size of the linked list.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know