LeetCode Hot 100 P142 Linked List Cycle II

---

Timeline

Timeline

2026-03-13

init

Linked list, two pointers

---

Problem:

P142 Linked List Cycle II

https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked

At the first meeting, the fast pointer has walked2 * ksteps, and the slow pointer has walked k steps. Let the length outside the cycle be m, and the cycle length be L.

The fast pointer has traveled n more laps (nL) that isk = nL, that is, the slow pointer has walkednLsteps

If the slow pointer walks m more steps, then in total it has walkedm+nLsteps to reachm+nL= the cycle entrance

Note: do not use a do-while loop for the loop below, because a linked list may be a circular linked list, and the length outside the cycle is 0.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x)
                : val(x)
                , next(nullptr)
        {
        }
};

class Solution {
    public:
        ListNode *detectCycle(ListNode *head)
        {
                if (head == nullptr)
                        return nullptr;
                ListNode *low = head, *fast = head;

                do {
                        if (fast->next == nullptr || fast->next->next == nullptr)
                                return nullptr;

                        fast = fast->next->next;
                        low = low->next;

                } while (low != fast);

                // low == fast

                low = head;
                while (low != fast) {
                        fast = fast->next;
                        low = low->next;
                }

                return low;
        }
};