[/dsa/leetcode]

141 - Linked List Cycle

Friday, 18 September 2026

<easy> [problem]

Two pointers at different speeds close the gap by one node per step inside a loop, so a cycle is detected by a collision rather than by remembering where you have been.

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

Problem

Given the head of a linked list, determine if the list has a cycle in it. A cycle exists if some node can be reached again by continuously following next.

Input: head = [3,2,0,-4], pos = 1
Output: true

Input: head = [1,2], pos = 0
Output: true

Input: head = [1], pos = -1
Output: false

pos is the index the tail connects to, or -1 for no cycle. It is not passed to the function — it only describes how the test list was built.

Constraints:

  • The number of nodes is in the range [0, 10^4]
  • -10^5 <= Node.val <= 10^5
  • Solve it using O(1) memory

Approach

Floyd’s cycle detection. slow moves one node per step, fast moves two. If the list ends, fast falls off it and there is no cycle. If it doesn’t end, both pointers are eventually circling the same loop forever, and they will meet at the same node at some point.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr) return false;
        ListNode* slow = head, *fast = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow) return true;
        }
        return false;
    }
};
  • time: O(n) - fast covers the tail once, then at most one lap of the cycle
  • space: O(1) - two pointers, the list is not modified
quantinium © 2026