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?

---

If O(n) space can be used, we can use a set to store all nodes that have been visited. Then the first node that cannot be inserted into the set will be the start node. Here is another O(1) space solution: Assume the slow node and fast node meet at the kth node in the linked list. Then the steps for slow node is X + n * Y + K where X is the number of nodes before the start of the cycle and Y is the number of nodes in the cycle. And the steps for the fast node is X + m * Y + K. Therefore:

2 * (X + n * Y + K) == X + m * Y + K

X + K = (m - 2 * n) * Y

Hence, if we move forward from the meet point by X steps, it will be the start point. There is an image in the reference link that can help understand.

C++ Code:

/*
 * func: find_cycle_start
 * goal: find the start point of the cycle if there exists in the linked list
 * @param head: head node of the linked list
 * return: if there is no cycle, return NULL, else return that point
 */
ListNode *find_cycle_start(ListNode *head){
    ListNode *slow = head;
    ListNode *fast = head;
    //Find if there eixsts circle first
    while(slow != nullptr && fast != nullptr && fast->next != nullptr){
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast){
            break;
        }
    }
    if(fast == nullptr || fast->next == nullptr){
        return nullptr;
    }
    slow = head;
    while(slow != fast){
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
}

Python Code:

# func: find the start point of the cycle if there exists in the linked list
# @param head: head node
# @return: the start point of the cycle
def find_cycle_start(head):
    slow = head
    fast = head
    while slow and fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    if not fast or not fast.next:
        return None
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return fast

Reference Link:

1.水中的鱼: [LeetCode] Linked List Cycle II, Solution: http://fisherlei.blogspot.com/2013/11/leetcode-linked-list-cycle-ii-solution.html