Leetcode 142. Linked List Cycle II

Clarification

Okay, so first I’ll restate the problem. We are given the head of a linked list, and we need to return the node reference where the cycle begins. If there is no cycle, we return null.

So for example, if the list looks like:

3 -> 2 -> 0 -> 4
     ↑         ↓
     └─────────┘

then the cycle starts at node 2, so we return that node, not the value or index.

Can the list be empty?
What is the most important value for this problem? Is it time or space?

Brute-force Approach

A simple solution is to use a hash set. We traverse the linked list and store every node we have visited. If we see the same node again, that node must be the cycle entrance. That gives us O(n) time, but it uses O(n) space.

Optimized Approach

The optimal solution is to use two pointer technique, in particular fast and slow pointer approach.

First, I use two pointers: fast and slow and set them to the head of the list. slow moves one step each time, and fast moves two steps each time. If there is no cycle, eventually fast or fast.next will reach the end of the list. If there is a cycle, slow and fast must meet somewhere inside the cycle. After they meet, the key trick is: move one pointer back to head, and keep the other pointer at the meeting point. Then move both one step at a time. The place where they meet again is the cycle entrance.

Now I’ll explain why this works.

• Suppose the distance from head to the cycle entrance is a.
• Then suppose the distance from the cycle entrance to the meeting point is b.
• And the rest of the cycle length is c.

So the cycle length is b + c. When slow and fast meet, slow has moved: a + b; fast has a + b + k(b + c) where k >= 1. Since fast moves twice faster than slow, that gives us a key observation: a + b = k(b + c), which is a = (k - 1)(b + c) + c. So if one pointer starts from head, and the other starts from the meeting point, they will meet at the cycle entrance after moving one step at a time because the pointer on the cycle will move k - 1 cycles and c steps, stopping at exact the cycle entrance.

Let me test it with an example that has an cycle:

3 -> 2 -> 0 -> 4
     ↑         ↓
     └─────────┘

slow and fast will first meet at 4 inside the cycle. Then I reset one pointer to head, move both one step at a time, and they meet at 2. Correct.

The time complexity would be O(n) because slow pointer moves less than 2n nodes. The space complexity is O(1).

Code

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                fast = head;
                while (fast != slow) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}

Follow-up

As a follow-up, if memory was not constrained, the hash set solution is simpler and easier to reason about, but fast and slow pointer is better because it solves the problem without extra space.