How do you solve Linked List Cycle II on LeetCode?

Linked List Cycle II (LeetCode #142) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Using a set to track visited nodes can be memory-intensive.

What is the brute force solution for Linked List Cycle II?

The brute force approach for Linked List Cycle II is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute-force approach involves checking each node to see if it can be reached again by following the next pointers. This is simple but inefficient, as it requires checking every node against every other node. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Linked List Cycle II?

Linked List Cycle II uses the following concepts: Hash Table, Linked List, Two Pointers. The recommended patterns to study are: Hash Map, Two Pointers.

What are the interview tips for Linked List Cycle II?

Explain your thought process clearly while coding. Consider edge cases, such as an empty list or a single node. Practice explaining the algorithm to someone else to solidify your understanding.

What are common mistakes when solving Linked List Cycle II?

Not handling the case where the list is empty. Failing to reset the slow pointer to head after detecting a cycle.

#142

Linked List Cycle II

Medium

Hash TableLinked ListTwo PointersHash MapTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses Floyd's Tortoise and Hare algorithm, which involves two pointers moving at different speeds. This allows us to detect a cycle efficiently without extra space.

⚙️

Algorithm

4 steps

1Step 1: Initialize two pointers, slow and fast. Both start at the head of the linked list.
2Step 2: Move slow by one step and fast by two steps until they meet or fast reaches the end.
3Step 3: If they meet, it indicates a cycle. To find the start of the cycle, reset one pointer to head and move both pointers one step at a time until they meet again.
4Step 4: The meeting point is the start of the cycle.

solution.py20 lines

1# Full working Python code
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7def detectCycle(head):
8    slow = fast = head
9    while fast and fast.next:
10        slow = slow.next
11        fast = fast.next.next
12        if slow == fast:
13            break
14    else:
15        return None
16    slow = head
17    while slow != fast:
18        slow = slow.next
19        fast = fast.next
20    return slow

ℹ

Complexity note: The time complexity is O(n) because in the worst case, we traverse the list twice. The space complexity is O(1) since we only use two pointers.

1Using a set to track visited nodes can be memory-intensive.
2Floyd's Tortoise and Hare algorithm is efficient for cycle detection.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.