Linked List Cycle II
Linked List Cycle II is a medium linked list problem solved with the slow fast pointers pattern.
The best approach, optimal (floyd, then reset one pointer), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from hash set up.
Problem
Return the node where a linked list’s cycle begins, or null if there is no cycle. Do not modify the list.
Examples
Example 1
- Input
head = [3, 2, 0, -4], tail connects to index 1- Output
the node with value 2
Example 2
- Input
head = [1, 2], no cycle- Output
null
Constraints
- The list has
0to10^4nodes. - Do not modify the list. Follow-up: O(1) memory.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 6 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Hash set | O(n) | O(n) |
| Optimal (Floyd, then reset one pointer) | O(n) | O(1) |
1Hash set
O(n)O(n)The first node you visit twice is where the cycle begins.
- Walk the list adding nodes to a set; return the first repeated node.
class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> seen = new HashSet<>();
for (ListNode p = head; p != null; p = p.next)
if (!seen.add(p)) return p;
return null;
}
}class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
seen = set()
p = head
while p:
if p in seen:
return p
seen.add(p)
p = p.next
return Noneclass Solution {
public:
ListNode* detectCycle(ListNode* head) {
unordered_set<ListNode*> seen;
for (ListNode* p = head; p != nullptr; p = p->next)
if (!seen.insert(p).second) return p;
return nullptr;
}
};function detectCycle(head) {
const seen = new Set();
for (let p = head; p !== null; p = p.next) {
if (seen.has(p)) return p;
seen.add(p);
}
return null;
}2Optimal (Floyd, then reset one pointer)
O(n)O(1)Find a meeting point with slow and fast. If the head is a steps from the cycle start and they meet b steps into the cycle of length c, then 2(a + b) = a + b + k·c, so a = k·c - b. A pointer from the head and one from the meeting point, both moving one step, meet at the cycle start.
- Run slow and fast until they meet (or return null).
- p = head; while p != slow: p = p.next; slow = slow.next.
- Return p.
class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p = head;
while (p != slow) { p = p.next; slow = slow.next; }
return p;
}
}
return null;
}
}class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
p = head
while p is not slow:
p = p.next
slow = slow.next
return p
return Noneclass Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode* p = head;
while (p != slow) { p = p->next; slow = slow->next; }
return p;
}
}
return nullptr;
}
};function detectCycle(head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let p = head;
while (p !== slow) { p = p.next; slow = slow.next; }
return p;
}
}
return null;
}Edge cases to test
- The cycle starts at the head
- Self-loop on a single node
Hints
Hint 1
After slow and fast meet, the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (going around).
FAQ
What is the best time complexity for Linked List Cycle II?
Optimal (Floyd, then reset one pointer) runs in O(n) time and O(1) extra space.
Which pattern does Linked List Cycle II use?
It is a linked list problem that uses the slow fast pointers pattern. Other problems with the same pattern: Middle of the Linked List, Linked List Cycle, Find the Duplicate Number.
Is there a brute force solution for Linked List Cycle II?
Yes. Hash set takes O(n) time and O(n) space. The first node you visit twice is where the cycle begins.
Which edge cases should I test for Linked List Cycle II?
The cycle starts at the head; Self-loop on a single node.