The challenge
Return the node where a linked list cycle begins, or null when the list is acyclic.
Use node identity and leave all next pointers unchanged.
Example
1 → 2 → 3 → 4 → node 2 returns node 2.
Use the walkthrough below to inspect the input and each state change.
See Cycle entry, step by step
Follow the pointers. Watch each link change.
A1Inspect node links
| Node | Value | Next |
|---|---|---|
| A1 | 1 | A2 |
| A2 | 2 | A3 |
| A3 | 3 | A4 |
| A4 | 4 | A2 |
Read the input
IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.
Start from the input head pointers.View original input
A: 1 (A1) → 2 (A2) → 3 (A3) → 4 (A4); parameters: {"cycleAt":1}
Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.
Put it into code
After Floyd’s meeting, equal-speed pointers from head and the meeting point converge at the entry.
Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def cycle_entry(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
entry = head
while entry is not slow:
entry = entry.next
slow = slow.next
return entry
return None
#include <cstddef>
struct Node {
int val;
Node* next;
Node(int value = 0, Node* link = nullptr)
: val(value), next(link) {}
};
Node* cycle_entry(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
Node* entry = head;
while (entry != slow) {
entry = entry->next;
slow = slow->next;
}
return entry;
}
}
return nullptr;
}