mediumLinked ListPattern: Floyd's Cycle Detection
Minimal Node Identification within a Cyclic Linked List Solution
Problem Statement
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
Example 1:
Input:head = [12, 45, 7, 22], pos = 1
Output:null
Explanation: The cycle consists of nodes with values [45, 7, 22]. The node with the minimum value among these is the one with value 7.
Example 2:
Input:head = [8, 15, 3, 9], pos = -1
Output:null
Explanation: The list terminates and does not contain a cycle.
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.
Time: O(N) Space: O(1)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def minimal_node_identification_within_a_cyclic_linked_list(head):
if not head or not head.next:
return None
slow, fast = head, head
has_cycle = False
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
has_cycle = True
break
if not has_cycle:
return None
min_node = slow
curr = slow.next
while curr != slow:
if curr.val < min_node.val:
min_node = curr
curr = curr.next
return min_node