easyLinked ListPattern: Slow & Fast Pointer
LinkedList Cycle Detection II Solution
Problem Statement
Given the head of a singly linked list, return the node where the cycle begins. If there is no cycle, return null. A cycle in a linked list is defined as a node that has a reference to a previously visited node in the list. This problem involves detecting if a cycle exists within a linked list and, if so, identifying the specific node where the cycle originates. The input is the head node of the linked list. The output should be the node where the cycle begins, or null if no cycle is present.
Examples
Example 1:
Input:head = [3,2,0,-4], pos = 1
Output:null
Explanation: The linked list has a cycle starting at node 2. Node 3 points to Node 2, Node 2 points to Node 0, Node 0 points to Node -4, and Node -4 points back to Node 2. Thus, the cycle begins at Node 2.
Example 2:
Input:head = [1,2], pos = 0
Output:null
Explanation: The linked list has a cycle starting at node 1. Node 1 points to Node 2, and Node 2 points back to Node 1. Thus, the cycle begins at Node 1.
Example 3:
Input:head = [1], pos = -1
Output:null
Explanation: The linked list has no cycle. The list ends after the node with value 1.
Constraints
- The number of nodes in the list is in the range [0, 10^4].
- Node values can range from -10^5 to 10^5.
- pos is -1 or a valid index in the linked list.
Time: O(N) Space: O(1)
Use Floyd's Tortoise and Hare algorithm. Two pointers, a slow one moving one step at a time and a fast one moving two steps, are used. If they meet, a cycle exists. To find the cycle's start, reset the slow pointer to the head and move both pointers one step at a time until they meet again; this meeting point is the cycle's start.
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 detect_cycle(head):
if not head or not head.next:
return None
slow = head
fast = head
# Phase 1: Detect if a cycle exists
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# Cycle detected
break
# If no cycle was detected
if slow != fast:
return None
# Phase 2: Find the start of the cycle
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow