Terminal Node Detection in Circular Singly Linked Lists — Problem Statement & Solution Guide
Problem Description
Given the head of a singly linked list, determine if the list contains a cycle. If a cycle exists, return the node where the cycle begins. A cycle exists if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that the tail's next pointer is connected to. Do not modify the list structure.
Examples
Input
head = Node(1, Node(2, Node(3, Node(4))))
Output
Node(4)
Explanation: Step-by-step: We start at the head node (1). We traverse the list until we reach node 4. We then detect a cycle by checking if the next pointer of node 4 points back to node 1. If it does, we return node 4 as the node where the cycle begins.
Input
head = Node(1, Node(2, Node(3)))
Output
null
Explanation: Step-by-step: We start at the head node (1). We traverse the list until we reach the last node (3). We then check if the next pointer of node 3 points back to node 1. If it does not, we return null because there is no cycle in the list.
Constraints
- The number of nodes in the list is in the range [0, 10^4].
- -10^5 <= Node.val <= 10^5
- pos is -1 or a valid index in the linked list.
Optimal Approach & Strategy
The optimized approach uses Floyd's cycle-finding algorithm, also known as the 'tortoise and the hare' algorithm. This algorithm uses two pointers that move at different speeds to detect the cycle. The time complexity of this approach is O(n), where n is the number of nodes in the list.
Brute Force Approach
The brute force approach involves using a Set to store the visited nodes. If a node is already in the Set, it means we have encountered a cycle and we can return the node. However, this approach has a high space complexity. Alternatively, we can also use a recursive approach with a depth-first search to detect the cycle.
Verified 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.