Minimal Node Identification within a Cyclic Linked List — Problem Statement & Solution Guide
Problem Description
Given the head of a singly linked list that may contain a cycle, determine if a cycle exists. If a cycle is present, return the node containing the minimum value among all nodes within the cyclic portion of the list. If no cycle exists, return null.
Examples
Input
Input: head = [3,2,0,-4], cycle = [2,0,-4,3]
Output
null
Explanation: Step 1: Initialize two pointers, slow and fast, to the head of the linked list. Step 2: Move the slow pointer one node at a time and the fast pointer two nodes at a time. Step 3: If the fast pointer reaches the end of the linked list, it means there is no cycle. Step 4: If the fast pointer meets the slow pointer, it means there is a cycle. Step 5: Find the start of the cycle by resetting the slow pointer to the head and keeping the fast pointer at the meeting point. Step 6: Move both pointers one node at a time. Step 7: The point where they meet again is the start of the cycle. Step 8: Find the node with the minimum value in the cycle by moving the slow pointer to the start of the cycle and the fast pointer to the node after the start of the cycle. Step 9: Move both pointers one node at a time. Step 10: The node with the minimum value is the node where the fast pointer meets the slow pointer.
Input
Input: head = [1,2,3,4,5,6,7,8,9,10]
Output
null
Explanation: Step 1: Initialize two pointers, slow and fast, to the head of the linked list. Step 2: Move the slow pointer one node at a time and the fast pointer two nodes at a time. Step 3: If the fast pointer reaches the end of the linked list, it means there is no cycle. Step 4: If the fast pointer meets the slow pointer, it means there is a cycle. Step 5: Find the start of the cycle by resetting the slow pointer to the head and keeping the fast pointer at the meeting point. Step 6: Move both pointers one node at a time. Step 7: The point where they meet again is the start of the cycle. Step 8: Since there is no cycle, return null.
Constraints
- The number of nodes in the list is in the range [0, 5000].
- -10^6 <= Node.val <= 10^6
- Your algorithm must use O(1) auxiliary space.
Optimal Approach & Strategy
Use Floyd's Cycle-Finding Algorithm with two pointers to detect the cycle in O(N) time and O(1) space. Upon finding the intersection, traverse the cyclic segment specifically to identify the minimum value.
Brute Force Approach
Store every visited node's reference in a Hash Set to detect a cycle. If a cycle is found, iterate through the set to find the minimum value, though this requires O(N) extra space.
Verified Code Solutions
function minimalNodeIdentificationWithinACyclicLinkedList(head) {
if (!head || !head.next) return null;
let slow = head, fast = head;
while (fast && fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let minNode = slow;
let curr = slow.next;
while (curr !== slow) {
if (curr.val < minNode.val) minNode = curr;
curr = curr.next;
}
return minNode;
}
}
// Check if a cycle exists but was not detected within the first three nodes
if (fast && fast.next) {
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
let minNode = slow;
let curr = slow.next;
while (curr !== slow) {
if (curr.val < minNode.val) minNode = curr;
curr = curr.next;
}
return minNode;
}
return null;
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* findMinInCycle(ListNode* head) {
if (!head) return nullptr;
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode* minNode = slow;
ListNode* curr = slow->next;
while (curr != slow) {
if (curr->val < minNode->val) {
minNode = curr;
}
curr = curr->next;
}
return minNode;
}
}
return nullptr;
}
};class Solution {
public ListNode detectCycle(ListNode head) {
if (!head || !head.next) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (!fast || !fast.next) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
// Detect cycle and find start of cycle
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
// Find node with minimum value in cycle
int min_val = Integer.MAX_VALUE;
ListNode min_node = null;
while (true) {
if (slow.val < min_val) {
min_val = slow.val;
min_node = slow;
}
slow = slow.next;
if (slow == fast) {
break;
}
}
return min_node;
}
}def detectCycle(head):
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
# Detect cycle and find start of cycle
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
# Find node with minimum value in cycle
min_val = float('inf')
min_node = None
while True:
if slow.val < min_val:
min_val = slow.val
min_node = slow
slow = slow.next
if slow == fast:
break
return min_nodefunction minimalNodeIdentificationWithinACyclicLinkedList(head) {
if (!head || !head.next) return null;
let slow = head, fast = head;
while (fast && fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let minNode = slow;
let curr = slow.next;
while (curr !== slow) {
if (curr.val < minNode.val) minNode = curr;
curr = curr.next;
}
return minNode;
}
}
// Check if a cycle exists but was not detected within the first three nodes
if (fast && fast.next) {
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
let minNode = slow;
let curr = slow.next;
while (curr !== slow) {
if (curr.val < minNode.val) minNode = curr;
curr = curr.next;
}
return minNode;
}
return null;
}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.