#142

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Linked List Cycle II

Identify the start of a cycle in a linked list using pointer manipulation, efficiently handling edge cases without modifying the list.

hash table linked list two pointers

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; otherwise, return null. The linked list must not be altered, and cycle detection should consider all nodes reachable through the next pointer.

A cycle occurs if following next pointers eventually revisits a previous node. Internally, pos indicates the index of the node connected by the tail (0-indexed) or -1 if no cycle exists. You must implement an efficient approach using either a hash table or two-pointer strategy without changing node connections.

Examples

Example 1

Input: head = [3,2,0,-4], pos = 1

Output: tail connects to node index 1

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

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

There is no cycle in the linked list.

Constraints

The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked-list.

Solution Approach

Hash Table Approach

Traverse the list while storing each visited node in a hash set. If a node is revisited, that node is the cycle's start. This approach guarantees O(n) time and O(n) space but explicitly tracks every node to prevent infinite loops.

Two-Pointer (Floyd's Tortoise and Hare) Approach

Use a slow pointer moving one step and a fast pointer moving two steps. If they meet, a cycle exists. Reset one pointer to head and move both one step at a time; their meeting point is the cycle's starting node. This method provides O(n) time and O(1) space, leveraging linked-list pointer manipulation.

Edge Case Handling

Always check for empty lists or lists with a single node, as these cannot form a cycle. Ensure that pointer resets and movements avoid null references. Careful implementation avoids infinite loops or misidentifying the cycle start.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for both hash table and two-pointer approaches, scanning each node at most twice. Space is O(n) for the hash table method and O(1) for two-pointer technique. Pointer resets and step calculations dominate runtime, especially when the cycle starts near the head.

What Interviewers Usually Probe

Candidate recognizes pointer manipulation and cycle detection pattern immediately.
Candidate distinguishes between detecting a cycle and locating its start.
Candidate considers edge cases with null or single-node lists and avoids modifying the original list.

Common Pitfalls or Variants

Common pitfalls

Misidentifying the meeting point of fast and slow pointers as the cycle start.
Failing to handle empty lists or single-node lists, causing null pointer errors.
Using extra space unnecessarily when two-pointer solution suffices.

Follow-up variants

Return the cycle length instead of the starting node.
Detect multiple cycles in a list with added constraints.
Modify the list to mark visited nodes and detect the cycle, trading safety for space.

FAQ

What is the fastest approach for Linked List Cycle II?

The two-pointer method (Floyd's Tortoise and Hare) efficiently finds the cycle start with O(n) time and O(1) space.

Can we use a hash table to solve Linked List Cycle II?

Yes, storing visited nodes in a hash set allows detecting the cycle start but requires O(n) extra space.

How do we handle lists with no cycle?

Return null immediately after traversing without revisiting any node; two-pointer or hash table methods both handle this.

Does the problem allow modifying the linked list?

No, the list must remain unaltered to maintain pointer integrity for cycle detection.

Why is pointer manipulation important in Linked List Cycle II?

Correct pointer manipulation ensures detection of the cycle start without extra space, preventing infinite loops and null errors.

terminal

Solution

Solution 1: Two Pointers

We first use the fast and slow pointers to judge whether the linked list has a ring. If there is a ring, the fast and slow pointers will definitely meet, and the meeting node must be in the ring.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                ans = head
                while ans != slow:
                    ans = ans.next
                    slow = slow.next
                return ans

Continue Practicing

#141 linked list cycle #160 intersection of two linked lists #143 reorder list