Reference: LeetCode EPI 7.3
Difficulty: Medium

My Post: Potential Methods & Analysis (When you understand the process, coding is super easy)

Problem

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example:

1
2
3
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.

Note: Do not modify the linked list.

Follow up: Cau you solve it without using extra space? $O(1)$

Analysis

Hash Set

Time: $O(N)$
Space: $O(N)$ ❌

Mark Node

It modifies the linked list. ❌

Time: $O(N)$
Space: $O(1)$

Two Pointers

Reference: link

Why could slow and fast meet? See my analysis in 141. Linked List Cycle

Notations:

  • head: the head node of the list.
  • entry: the entry node of the cycle.
  • meeting: the intersected node at which slow and fast meet.
  • L1: the distance between head and entry.
  • L2: the distance between entry and meeting.
  • C: the length of the cycle.
  • n: how many times fast loops in the cycle.

Floyd’s Cycle Detection:

The first half is the same as in the two-pointer solution in Problem I. To find the entry point, we can start traversing from head and slow at the meeting point in tandem. The node they meet is the entry node.

Why is the node they meet the entry node?

When slow and fast meet,

  • slow moves L1 + L2. (head -> meeting)
  • fast moves L1 + L2 + n * C.

Since each time fast moves twice the step as slow does, when they meet at meeting node:

  • We have: 2 * Dis(slow) = 2 * (L1 + L2) = L1 + L2 + n * C = Dis(fast) => L1 + L2 = n * C.
  • Equivalent to: L1 = (n - 1) * C + (C - L2) where C - L2 is the distance between meeting and entry.
  • The equation indicates that if slow or fast now starts moving from meeting and a new node starts moving from head, they will finally meet at the entry node!
    • Consider a very big L1 and a relatively short C.
    • Note that (n - 1) * C means that slow or fast moves from meeting by n - 1 cycles and still stops at meeting.

Note:

  • It’d better to start slow and fast from the head both.
  • Move first! Otherwise, they must meet at the beginning.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode useTwoPointers(ListNode head) {
  ListNode slow = head;
  ListNode fast = head;
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (fast == slow) { // meets
      while (head != slow) { // moves from the head until they meet
        head = head.next;
        slow = slow.next;
      }
      return head;
    }
  }
  return null;
}

Time: $O(L1 + L2 + L1) < O(N + N + N) = O(3N) = O(N)$

  • Distance that slow moves before they meet: $O(L1 + L2)$
  • Distance that the new node moves after slow and fast meet: $O(L1)$

Space: $O(1)$