Introduction
In this blog post, we'll explore a popular problem from LeetCode: Linked List Cycle II. This problem is all about detecting the start of a cycle in a linked list. We will go through the problem description, understand two approaches to solve it, and then look at their implementations in Python.
Problem Statement
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null
.
A cycle in a linked list occurs when a node’s next
pointer points back to a previous node, creating a loop. The problem does not give us the position directly, so we need to determine if a cycle exists and find its starting point.
Approach 1: Using a Set
The first approach to solve this problem is by using a set to keep track of visited nodes. As we traverse the linked list, we add each node to the set. If we encounter a node that is already in the set, then that node is the start of the cycle.
Implementation
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
visited = set()
current = head
while current:
if current in visited:
return current
visited.add(current)
current = current.next
return None
Explanation
Approach 1: Using a Set
Initialization:
- Create an empty set called
visited
. - Initialize a variable
current
to the head of the list.
Cycle Detection:
- Traverse the list, adding each node to the
visited
set. - If a node is already in the set, it means we have encountered the start of the cycle.
- Return the node where the cycle begins.
- If the traversal ends (i.e.,
current
becomesNone
), returnNone
as there is no cycle.
Approach 2: Floyd’s Tortoise and Hare Algorithm
The second approach is using Floyd’s Cycle-Finding Algorithm, also known as the Tortoise and Hare algorithm. This method involves two main steps:
Detection of Cycle:
- Use two pointers, a slow pointer (
slow
) and a fast pointer (fast
). - Move
slow
by one step andfast
by two steps. - If there is a cycle,
slow
andfast
will meet at some point inside the cycle.
Finding the Start of the Cycle:
- Once a cycle is detected, reset one pointer to the head of the linked list.
- Move both pointers one step at a time.
- The point at which they meet is the start of the cycle.
Implementation
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head:
return None
slow, fast = head, head
while True:
if not fast or not fast.next:
return None
slow = slow.next
fast = fast.next.next
if slow == fast:
break
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return fast
Explanation
Initialization:
- Check if the head is
None
. If it is, there’s no cycle, and we returnNone
.
Cycle Detection:
- Initialize two pointers,
slow
andfast
, both pointing to the head of the list. - Traverse the list with
slow
moving one step at a time andfast
moving two steps. - If
fast
orfast.next
becomesNone
, there’s no cycle, and we returnNone
. - If
slow
equalsfast
, a cycle is detected.
Finding the Start Node:
- Reset
fast
to the head of the list. - Move both
slow
andfast
one step at a time until they meet. - The node where they meet is the start of the cycle.
Conclusion
We have discussed two efficient methods to detect the start of a cycle in a linked list: using a set and Floyd’s Tortoise and Hare algorithm. Both methods have their own advantages and are useful in different scenarios.
- Using a Set: Simpler to understand and implement but uses O(n) extra space.
- Floyd’s Algorithm: More efficient in terms of space complexity (O(1)) but slightly more complex to implement.
I hope this explanation helps you understand how to tackle the Linked List Cycle II problem. Feel free to ask questions or share your thoughts in the comments!
Top comments (0)