Question

LeetCode Link | 142. Linked List Cycle II | Medium

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

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 (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Constraints

  • The number of the nodes in the list is in the range [0, 10^4].
  • -10^5 <= Node.val <= 10^5
  • pos is -1 or a valid index in the linked-list.

Examples

Example 1

Example 1

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2

Example 2

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Solution Approach

Method: Two-pointers

Constrains

  • None

This method does not have any limitations.

Concept Explanation

This question can be solve using stack to store the observed node and once it iterate into a loop, it will soon finds that by detecting that the node is already in the stack. It could be done in few lines as shown below:

1
2
3
4
5
6
7
8
9
10
11
function detectCycle(head: ListNode | null): ListNode | null {
    let stack = [];
    let curNode = head;
    while (curNode) {
      	// Check if exist in stack
        if (stack.includes(curNode)) return curNode;
        stack.push(curNode);
        curNode = curNode.next;
    }
    return null;
};

However, this used O(n) space in memory, and there is a more efficient way to solve it which only cost O(1) memory.

It needs some math calculations to make logic clear and complete. We will use fast & slow pointer to solve this. Both pointers start from the head, where fast pointer move 2 nodes each time, and slow pointer move 1 node each time.

In this way, fast pointer always enter the loop before slow pointer, which means if fast pointer meets slow pointer, they must meets in the loop. Thus, we can know if there is a loop in the list using fast & slow pointer.

How to detect a loop

But the question is, How to find the entry of the loop if we find there is a loop?

Here is what math appears, we assume the node distance from head to the entry of the loop is x, the node distance from entry of the loop to the node where two pointers meet is y, and the node distance from this node to the entry of the loop is z, which as the figure shown below:

Node Distance

When two pointers meet, slow pointer walked x + y node distances, fast pointer walked more than 1 cycles in the loop before slow pointer reaches here, which is x + y + n(y + z) node distances, where n stands number of cycle fast pointer walked.

Node distance:

  • Fast: x + y + n(y + z)
  • Slow: x + y

Since fast pointer walk 2 nodes every step where slow pointer only walk 1 node, we can say that fast walked twice as the slow walked. This could write as following:

1
2
3
4
5
"slow" * 2 = "fast"

(x + y) * 2 = x + y + n(y + z)

x + y = n(y + z) // subtract `x+y` on each side

We have to find where the entry of the loop is, which is the node has x distance to the head.

1
x = n(y + z) - y

We extract a (y + z) from n(y + z) to subtract remaining y at the right side of equation:

1
2
x = (n - 1)(y + z) - y + (y + z)
x = (n - 1)(y + z) + z

After rearranging the formula, it becomes: x = (n - 1)(y + z) + z. Note that 𝑛 must be greater than or equal to 1, because the fast pointer has to travel at least one extra loop to meet the slow pointer.

How we explain this equation?

Taking the case where 𝑛 = 1 as an example, it means that the fast pointer meets the slow pointer after one complete loop in the circle.

When 𝑛 is 1, the formula simplifies to x = z,

This implies that if a pointer starts from the head node and another pointer starts from the meeting node, and each pointer advances one node at a time, the location where these two pointers meet is the entry node of the loop.

Thus, at the meeting point, define one pointer index1, and at the head node, define another pointer index2.

Move index1 and index2 simultaneously, one node at a time, and the place where they meet will be the entry node of the loop.

Condition: n = 1

What if n is greater than 1?

In fact, this situation has the same effect as when n = 1. You can find the entry node of the loop using this method. The only difference is that the index1 pointer makes n-1 additional loops in the circle before meeting index2. Their meeting point is still the entry node of the loop.

Code

  • Time complexity: O(n)

    • Before the fast and slow pointers meet, the number of steps taken by the pointers is less than the length of the linked list. After the pointers meet, the number of steps taken by the two index pointers is also less than the length of the linked list. Overall, the total number of steps taken is less than 2n.

  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
    let slowNode: ListNode | null = head,
        fastNode: ListNode | null = head;
    while (fastNode !== null && fastNode.next !== null) {
        slowNode = slowNode!.next;
        fastNode = fastNode.next.next;
        if (slowNode === fastNode) {
            slowNode = head;
            while (slowNode !== fastNode) {
                slowNode = slowNode!.next;
                fastNode = fastNode!.next;
            }
            return slowNode;
        }
    }
    return null;
};

Conclusion

This problem not only tests operations on linked lists but also requires some mathematical calculations. It mainly examines two knowledge points: 1. Determining whether a linked list has a loop. 2. If there is a loop, how to find the entrance of this loop.