LeetCode Linked List Cycle II: The Mathematical Fact

Overview

slow/fast pointers are used to solve LeetCode Linked List Cycle II and the key mathematical fact is explained about why and how we find the start node.

LeetCode Linked List Cycle II

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

Follow up:
Can you solve it without using extra space?

The Mathematical Fact and Solution

Suppose there is a cycle in the linked list, and we still adopt the similar idea of slow/fast pointer as in “LeetCode Linked List Cycle: Two Pointers, Reversal and Hash“. We need to prove some key fact about the relationship between the start node and the meeting node.

Let H denote the head of the linked list, S denote the start node of the cycle, M denote the meet node for the slow and fast pointer. And let a denote the list length from H to the node just before S (i.e., the last node outside the cycle), let b denote the length from S to M both inclusively. And let c denote the length of the remaining list of the cycle, that is c + b would be the length of the cycle. Assume the steps the fast pointer takes are always strictly twice the slow pointer takes (note, here is a tricky part which leads to a small trick in the following code). We have the following relationship:

2 * (a + m * (b + c) + b) = a + n *(b + c) + b

where m denotes the number of cycles the slow pointer takes, and n is for the fast pointer. Now we have

a + b = (n - 2m)*(b + c) => a = c

The reason a = c is for your own to figure out. But the key fact is already here: after the slow and fast pointer meet at M node, as long as the take c more steps (one node at one time), they will reach the at the start node S, and since we do not know exactly the value c is, we need to put another point at the head, and make them start to proceed one step at a time and the same node they reaches is just the Start node of the cycle. Here is the accepted code by LeetCode OJ to pass this Linked List Cycle II problem, and be careful about the slow = slow->next statement (think about why?):

ListNode *detectCycle(ListNode *head) {
    if (NULL == head) return NULL;
    ListNode *slow = head;
    ListNode *fast = head->next;

    while (slow && fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (NULL == fast || NULL == fast->next) return NULL;

    fast = head;
    slow = slow->next; // Be careful!
    while (fast!= slow) slow = slow->next, fast = fast->next;
    return slow;
}

Summary

slow/fast pointers are used to solve LeetCode Linked List Cycle II and the key mathematical fact is explained about why and how we find the start node.

Written on December 8, 2014