Linked List Cycle: definition
A cycle exists when following next references brings you back to the same node. Detect a repeated node object, not a repeated value.
Task example: Linked List Cycle
Given head, return True if the linked list contains a cycle; otherwise return False. Each node has val and next. Do not change the list.
pos describes the tail connection in these examples. It is not passed to hasCycle(head). Indices identify nodes in the diagram; equal values can belong to different nodes.
The editor receives head as a ListNode object (or None). ListNode has val and next; the test runner builds the links for you.
Visited-node set: video explanation
values = [3, 2, 0, -4], pos = 1 → True
Prefer reading? Follow the steps below.
- Create an empty set. At each node, check whether that exact node object is already in the set. If yes, return True immediately.
- Otherwise, add the node and follow next. For [3, 2, 0, -4] with pos = 1, visit nodes #0, #1, #2, #3, then #1 again. That repeated node proves there is a cycle.
- If head reaches None, return False. Two separate nodes holding 7 do not form a cycle unless their links actually loop back.
Time complexity · O(n)
Each distinct node is processed at most once before a repeat or None. With average constant-time set operations, time complexity is O(n).
Space complexity · O(n)
The set can contain all n distinct nodes, so auxiliary space is O(n). We store references without changing node links.
Two pointers: video explanation
values = [3, 2, 0, -4], pos = 1 → True
Prefer reading? Follow the steps below.
- Start slow and fast at head. While fast and fast.next exist, move slow one link and fast two links. The guard prevents reading next from None.
- Compare slow is fast after moving. In this example, their index pairs are (1, 2), (2, 1), then (3, 3). They meet at node #3, so return True. The meeting node need not be the cycle entrance.
- If fast reaches the end, return False. An empty list has no cycle; a single node pointing to itself does. Compare node identity, never just val.
Why they meet: inside a cycle, fast gains one link on slow per iteration. The gap around a finite cycle must eventually reach zero. This keeps linear time while removing the visited-node set.
Time complexity · O(n)
Reaching the cycle takes O(n) steps. Once both pointers are inside, they meet within one cycle length. Without a cycle, fast reaches the end in O(n).
Space complexity · O(1)
Only slow and fast references are needed, regardless of list length. Auxiliary space is O(1); the original list is not modified.