Find the Starting Node of a Cycle in a Linked List

90.7k
0

Given head of a singly linked list, return the node where a cycle begins. Return null when no cycle exists.

A cycle exists when repeated movement through next pointers reaches an already visited node. The linked list structure must remain unchanged.

Example 1

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

Output: 2

Explanation: Tail connects to index 1, so cycle start value equals 2.

Example 2

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

Output: null

Explanation: Tail points to null, so no cycle exists.

Brute Force Approach

Hash set tracking stores every visited node address during linked list traversal. The first node address encountered twice marks cycle entry because traversal reaches repeated nodes only after entering a cycle.

Concepts include linked list traversal and hash set lookup. The method gives a direct correctness argument and handles empty lists, single-node cycles, and long acyclic prefixes without pointer arithmetic.

Algorithm

  • Initialize an empty hash set to store visited node addresses, as the address uniquely identifies each node and helps detect when the traversal reaches the same node again.

  • Initialize current as head, since the traversal needs to begin from the first node.

  • Traverse while current is not NULL, as every reachable node needs to be checked for repetition.

  • Return current when it already exists in the hash set, as encountering the same node address again confirms the start of a cycle.

  • Insert current into the hash set and move current to the next node, allowing the traversal to continue while recording every visited node.

  • Return NULL when the traversal reaches the end of the list, since reaching NULL means no node was revisited and therefore no cycle exists.

Dry Run

cycle start by hash set

cycle start by hash set

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode* next;
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Function to find cycle start using hash set.
ListNode* findStartingPoint(ListNode* head) {
unordered_set<ListNode*> visited;
ListNode* current = head;
// Traverse nodes until null or repeated address appears.
while (current != nullptr) {
if (visited.find(current) != visited.end()) {
return current;
}
visited.insert(current);
current = current->next;
}
return nullptr;
}
};
// Function to build linked list and connect tail using position.
ListNode* buildList(vector<int>& values, int pos) {
if (values.empty()) return nullptr;
vector<ListNode*> nodes;
for (int value : values) {
nodes.push_back(new ListNode(value));
}
for (int index = 0; index + 1 < (int)nodes.size(); index++) {
nodes[index]->next = nodes[index + 1];
}
if (pos >= 0) {
nodes.back()->next = nodes[pos];
}
return nodes[0];
}
// Driver code.
int main() {
vector<int> values = {3, 2, 0, -4};
int pos = 1;
ListNode* head = buildList(values, pos);
Solution sol;
ListNode* answer = sol.findStartingPoint(head);
if (answer == nullptr) cout << "null";
else cout << answer->data;
return 0;
}

Complexity Analysis

Time Complexity: O(N), traversal visits each unique node at most once before detecting repetition or reaching null.

Space Complexity: O(N), hash set can store every node address in the linked list.

Optimal Approach

Floyd cycle detection uses two pointers moving at different speeds. Slow pointer moves one step, while fast pointer moves two steps. A cycle forces both pointers to meet inside the cycle; an acyclic list lets fast pointer reach null.

After the first meeting, reset slow pointer to head and keep fast pointer at the meeting node. Move both pointers one step at a time. The meeting node in the second phase is the cycle entry, based on equal distance from head to entry and from meeting point to entry modulo cycle length.

Algorithm

  • Initialize slow and fast at head, as the two pointers will move at different speeds to determine whether a cycle exists and where it begins.

  • Traverse while fast and fast->next both exist, since these conditions allow fast to safely move two nodes at a time.

  • Move slow one node and fast two nodes in each iteration, as a cycle will eventually make the faster pointer catch up with the slower pointer.

  • When slow and fast meet, reset slow to head, since the distance from the head to the cycle start relates to the distance from the meeting point to the cycle start.

  • Move both slow and fast one node at a time until they meet again, as this meeting point is the first node of the cycle.

  • Return the meeting node as the cycle start, since both pointers now converge exactly at the beginning of the cycle.

  • Return NULL when fast reaches the end of the list, as reaching NULL confirms that no cycle exists.

Dry Run

starting point

starting point

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode* next;
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Function to find cycle start using Floyd algorithm.
ListNode* findStartingPoint(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
// Detect cycle by moving pointers at different speeds.
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
slow = head;
// Move both pointers equally to reach cycle entry.
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return nullptr;
}
};
// Function to build linked list and connect tail using position.
ListNode* buildList(vector<int>& values, int pos) {
if (values.empty()) return nullptr;
vector<ListNode*> nodes;
for (int value : values) {
nodes.push_back(new ListNode(value));
}
for (int index = 0; index + 1 < (int)nodes.size(); index++) {
nodes[index]->next = nodes[index + 1];
}
if (pos >= 0) {
nodes.back()->next = nodes[pos];
}
return nodes[0];
}
// Driver code.
int main() {
vector<int> values = {3, 2, 0, -4};
int pos = 1;
ListNode* head = buildList(values, pos);
Solution sol;
ListNode* answer = sol.findStartingPoint(head);
if (answer == nullptr) cout << "null";
else cout << answer->data;
return 0;
}

Complexity Analysis

Time Complexity: O(N), pointer movement remains linear across detection and entry-location phases.

Space Complexity: O(1), only slow and fast pointers are used.

Interview follow-up Questions

This problem is a follow-up to Detect a Loop in Linked List, where Floyd's Cycle Detection algorithm is used to determine whether a cycle exists. Once a cycle is detected, the same technique is extended to find its starting node. Q2. Can a single node form a cycle? Yes. If a node's next pointer points back to itself, it forms a cycle, and that node is also the starting node of the cycle.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links inste...

59.9k
Linked List

Merge Two Sorted Linked Lists

Given heads of two sorted linked lists, merge both lists into one sorted linked list and return the head of the merged list. Every node stores an integer value and a pointer to the next node. The f...

114.6k
Linked List

Find pairs with given sum in Doubly Linked List

Input: DLL = [1, 2, 4, 5, 6, 8], target = 7 Output: [[1, 6], [2, 5]] Explanation: Values 1 and 6 form sum 7. Values 2 and 5 also form sum 7. Input: DLL = [1, 3, 5, 7, 9], target = 10 Output: [[1, 9...

101.5k
Comments0