Description
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list 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 tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
Examples:
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.Solution in Python
To solve the problem of detecting the node where a cycle begins in a linked list, we can use Floyd’s Tortoise and Hare algorithm. This algorithm allows us to detect a cycle using two pointers (slow and fast) and then find the starting node of the cycle.
- Detect if a cycle exists:
- Use two pointers,
slowandfast. Initially, both pointers point to the head of the linked list. - Move
slowpointer by one step andfastpointer by two steps. - If there is a cycle,
slowandfastpointers will eventually meet inside the cycle. - If
fastpointer reaches the end of the list (i.e.,fastorfast.nextbecomesNone), there is no cycle in the list.
- Use two pointers,
- Find the entry point of the cycle:
- If
slowandfastpointers meet, there is a cycle. To find the starting node of the cycle:- Move one pointer back to the head of the list and keep the other pointer at the meeting point.
- Move both pointers one step at a time. The node where they meet is the start of the cycle.
- If
Python
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Step 1: Detect if a cycle exists
if not head or not head.next:
return None
slow = head
fast = head
# Move slow by 1 step and fast by 2 steps
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# If slow and fast meet, there is a cycle
if slow == fast:
# Step 2: Find the entry point of the cycle
# Move one pointer to the head
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
# Both pointers now point to the start of the cycle
return slow
# If we reach here, it means there is no cycle
return NoneDetailed Explanation
- Cycle Detection:
- Initialize
slowandfastpointers to the head of the linked list. - Iterate through the list: move
slowby one node andfastby two nodes. - If
slowandfastmeet, it confirms the presence of a cycle.
- Initialize
- Finding the Start of the Cycle:
- Move
slowpointer to the head of the list. - Move both
slowandfastpointers one step at a time until they meet. - The meeting point is the start of the cycle.
- Move
This approach ensures that we detect the cycle in O(n) time complexity and use only O(1) additional space, as required.
Solution in Javascript
JavaScript
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
// Step 1: Detect if a cycle exists
if (!head || !head.next) {
return null;
}
let slow = head;
let fast = head;
// Move slow by 1 step and fast by 2 steps
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
// If slow and fast meet, there is a cycle
if (slow === fast) {
// Step 2: Find the entry point of the cycle
// Move one pointer to the head
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
// Both pointers now point to the start of the cycle
return slow;
}
}
// If we reach here, it means there is no cycle
return null;
};Solution in Java
Java
public class Solution {
public ListNode detectCycle(ListNode head) {
// Step 1: Detect if a cycle exists
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
// Move slow by 1 step and fast by 2 steps
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
// If slow and fast meet, there is a cycle
if (slow == fast) {
// Step 2: Find the entry point of the cycle
// Move one pointer to the head
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
// Both pointers now point to the start of the cycle
return slow;
}
}
// If we reach here, it means there is no cycle
return null;
}
}Solution in C#
C#
public class Solution {
public ListNode DetectCycle(ListNode head) {
// Step 1: Detect if a cycle exists
if (head == null || head.next == null) {
return null; // If the list is empty or has only one node, no cycle
}
ListNode slow = head; // Initialize slow pointer
ListNode fast = head; // Initialize fast pointer
// Move slow pointer by 1 step and fast pointer by 2 steps
while (fast != null && fast.next != null) {
slow = slow.next; // Move slow pointer by 1 step
fast = fast.next.next; // Move fast pointer by 2 steps
// If slow and fast meet, a cycle exists
if (slow == fast) {
// Step 2: Find the entry point of the cycle
// Move one pointer to the head
slow = head;
while (slow != fast) {
slow = slow.next; // Move slow pointer by 1 step
fast = fast.next; // Move fast pointer by 1 step
}
// Both pointers now point to the start of the cycle
return slow;
}
}
// If we reach here, it means there is no cycle
return null;
}
}