mediumLinked ListPattern: Floyd's Cycle Detection
Terminal Node Detection in Circular Singly Linked Lists Solution
Problem Statement
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
Example 1:
Input:head = [17, 24, 8, 31], pos = 1
Output:null
Explanation: There is a cycle in the list where the tail points to the second node (index 1), which has a value of 24.
Example 2:
Input:head = [5, 12], pos = 0
Output:null
Explanation: The tail connects back to the first node (index 0), forming a cycle beginning at 5.
Example 3:
Input:head = [1], pos = -1
Output:null
Explanation: There is no cycle in the linked 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.
Time: O(n) Space: O(1)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
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 slow