Terminal Node Detection in Circular Singly Linked Lists — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Detect cycle using slow/fast pointers
O(n)O(1)Problem Description
You are provided with an array values of length n representing the sequential data stored in a singly linked list. Additionally, you are given an integer pos which specifies the zero-based index of the node where the next pointer of the last node in the list is connected. If pos is -1, the list is acyclic and terminates with a null pointer. Your task is to identify the zero-based index of the first node that is part of the cycle. If the list does not contain a cycle, return -1.
The list is constructed such that node i points to node i+1 for all 0 <= i < n-1. The next pointer of the last node (index n-1) points to the node at index pos if pos != -1, or to null otherwise. Note that the cycle, if it exists, always includes the last node and the node at index pos.
Return the index of the node where the cycle begins. This is the first node encountered when traversing the list from the head that is part of the circular loop.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Terminal Node Detection in Circular Singly Linked Lists"
WHY DOES IT MATTER?
Cycle detection is a fundamental pattern in linked data structures, graph traversal, and even in distributed systems where loops can cause deadlocks or resource leaks. Mastering the two‑pointer technique equips engineers to handle these scenarios with optimal time and space guarantees.
OPTIMIZATION CHALLENGE
The breakthrough is realizing that two pointers moving at different speeds will inevitably collide inside a cycle, and that the distance from the head to the cycle entry equals the distance from the collision point to the entry. This insight eliminates the need for extra storage.
REAL-WORLD CONNECTION
Think of a network of microservices where each service forwards a request to the next. If a request loops back to a previous service, it creates a circular dependency that can exhaust resources—detecting that loop mirrors cycle detection in linked lists.
During an interview, start by stating the naive hash‑set solution, then immediately pivot to Floyd’s algorithm, explaining both the meeting phase and the entry‑node phase; this demonstrates depth of understanding and awareness of space constraints.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
In a singly linked list, each node points to exactly one successor, which makes traversals straightforward—simply follow the next pointers until a null is encountered. However, when the list contains a cycle, the traversal never reaches null, leading to infinite loops. Detecting a cycle efficiently relies on the Floyd’s Tortoise and Hare algorithm, which uses two pointers moving at different speeds; if a cycle exists, the fast pointer will eventually lap the slow pointer. Once a meeting point is found, resetting one pointer to the head and advancing both one step at a time guarantees they meet at the cycle’s entry node, which is the terminal node in the context of a circular singly linked list. Naïve approaches, such as marking visited nodes in a hash set, achieve O(n) time but require O(n) extra space, which becomes prohibitive for massive lists or memory‑constrained environments, whereas the two‑pointer technique delivers O(1) auxiliary space.
Interview Questions on This Problem
Q1How would you detect a cycle in a singly linked list without using extra memory, and how can you locate the exact node where the cycle begins?
Use Floyd’s Tortoise and Hare: advance a slow pointer by one step and a fast pointer by two steps. If they meet, a cycle exists. Then move one pointer back to the head and advance both one step at a time; their next meeting point is the cycle’s entry node.
Q2Given the array representation of a linked list and a position index where the last node points, how can you compute the index of the terminal node in O(1) space?
Construct the list virtually using the array and the pos value. Apply the two‑pointer technique directly on the virtual list: treat array indices as node identifiers, move pointers according to next‑index logic, and follow the same meeting‑then‑reset steps to obtain the terminal index.
Q3Why might a hash‑set based cycle detection fail in a production system handling billions of nodes, and what alternative does the two‑pointer method provide?
A hash set stores each visited node, consuming O(n) memory, which can exceed available RAM for billions of nodes, causing out‑of‑memory crashes. The two‑pointer method uses only two pointers, achieving O(1) extra space, making it scalable for massive data streams.
Examples
Input
values = [10, 20, 30, 40, 50], pos = 2
Output
2
Explanation: The list is 10 -> 20 -> 30 -> 40 -> 50. The last node (50) points to the node at index 2 (30). The cycle is 30 -> 40 -> 50 -> 30. The first node in the cycle is at index 2.
Input
values = [1, 2, 3, 4, 5, 6], pos = 0
Output
0
Explanation: The list is 1 -> 2 -> 3 -> 4 -> 5 -> 6. The last node (6) points to the head (1). The cycle is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 1. The first node in the cycle is at index 0.
Input
values = [7, 8, 9], pos = -1
Output
-1
Explanation: The list is 7 -> 8 -> 9 -> null. Since pos is -1, there is no cycle. Return -1.
Input
values = [100, 200, 300, 400], pos = 3
Output
3
Explanation: The list is 100 -> 200 -> 300 -> 400. The last node (400) points to itself (index 3). The cycle is 400 -> 400. The first node in the cycle is at index 3.
Constraints
- 1 <= values.length <= 10^5
- -10^9 <= values[i] <= 10^9
- -1 <= pos < values.length
Optimal Approach & Strategy
Use Floyd’s Tortoise and Hare algorithm: two pointers with different speeds detect a meeting point, then a second pass from head finds the exact start of the cycle.
Brute Force Approach
Traverse the list while storing each visited node in a hash set; if you encounter a node already in the set, a cycle is found and that node is the entry point.
Code Solutions
function terminalNodeDetectionInCircularSinglyLinkedList(head) {
if (!head || !head.next) {
return null;
}
let slow = head;
let fast = head.next;
while (slow !== fast) {
if (!fast || !fast.next) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
let prev = head;
while (prev.next !== slow.next) {
prev = prev.next;
slow = slow.next;
}
return prev;
}ListNode* terminalNodeDetectionInCircularSinglyLinkedList(ListNode* head) {
if (!head || !head->next) {
return nullptr;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (!fast || !fast->next) {
return nullptr;
}
slow = slow->next;
fast = fast->next->next;
}
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}public class Solution {
public ListNode terminalNodeDetectionInCircularSinglyLinkedList(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}class Solution:
def terminal_node_detection_in_circular_singly_linked_list(self, head: ListNode) -> ListNode:
if not head or not head.next:
return None
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return None
slow = slow.next
fast = fast.next.next
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slowfunction terminalNodeDetectionInCircularSinglyLinkedList(head) {
if (!head || !head.next) {
return null;
}
let slow = head;
let fast = head.next;
while (slow !== fast) {
if (!fast || !fast.next) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
let prev = head;
while (prev.next !== slow.next) {
prev = prev.next;
slow = slow.next;
}
return prev;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.