[/dsa/leetcode]

142 - Linked List Cycle II

Wednesday, 16 September 2026

<medium> [problem]

Floyd's cycle detection on an actual linked list - the same two phases as 287, with the null checks a real list needs.

{linked list}{two pointers}{cycle detection}

Problem

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.

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1

Input: head = [1,2], pos = 0
Output: tail connects to node index 0

Input: head = [1], pos = -1
Output: no cycle

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

Follow-up: can you solve it using O(1) memory?

Approach

We use the Floyd’s Linked List Cycle Finding Algorithm. Two pointers are just to first find the node that is in the cycle. After finding the node, we make the slow pointer start from begining and the fast pointer moves one step at a time. Thus when both the pointer collide, we would find the node that started the cycle.

class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};
0 → 1 → 2 → 3 → 4 → 5
        ↑           │
        └───────────┘
  • a is the tail length: steps from the head to the cycle entrance. Here a = 2 (node 0 → node 2).
  • c is the cycle length. Here c = 4 (2 → 3 → 4 → 5 → back to 2).
  • b is how far past the entrance the pointers meet. You find it by running phase 1.

The slow pointer has walked a + b and the fast exactly twice that, so their difference is a whole number of laps and a + b is a multiple of 2(a + b) − (a + b) = a + b = x * c. From the collision, a more steps completes a lap and arrives at the entrance — and a steps from the head arrives there too, so both pointers land together.

  • time: O(n) — phase one is at most a + c steps, phase two at most a
  • space: O(1) — two pointers, and the list is never modified
quantinium © 2026