Link: https://leetcode.com/problems/linked-list-cycle-ii/

Solutions

Hash Table

The first intuitive solution is to use a hash table. As we iterate through the linked list, we store the node in the hash table. If the current node is already in the hash table, it means there is a cycle.

ListNode *detectCycle(ListNode *head) {
    map<ListNode*, bool> m;
    
    while (head != nullptr) {
        if (m[head]) {
            return head;
        }
        m[head] = true;
        head = head->next;
    }
    
    return nullptr;
}

Two Pointers with some maths

There is a good method to check if there is a cycle in the linked list. It is to use a slow pointer that moves 1 step at a time and a fast pointer that moves 2 steps at a time. If there is a cycle, they will eventually meet. Otherwise, the fast pointer will reach the nullptr first and the program ends. This is actually the LeetCode #141 question.

In addition to the above method, we can adopt two methods to find the start of the cycle.

Method 1

1. Use the two pointers method to find the meeting point.
2. Calculate the length of the cycle.
3. Use two pointers in which one starts from the head and the another moves the length of the cycle steps in advance. Then they start to move 1 step at a time. They will meet at the start of the cycle since the lenth of the linked list is equal to the length between the head and the start of the cycle plus the length of the cycle.

한국어 자료로도 좋은 설명을 해주신 분이 계셔서 유튜브 링크를 남깁니다.

Method 2

If we need to reduce the constant of the time complexity, we can use some maths.

Let define the following:

1. $L_1$: the length between the head and the start of the cycle.
2. $L_2$: the length between the start of the cycle and the meeting point of two pointers.
3. $C$: the length of the cycle.
4. $N$: the number of cycles.

We can get the following equations:

So, how to interpret this? If we send a pointer from the head and another pointer from the previous meeting point, they will meet at the start of the cycle.

ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head;
    ListNode *fast = head;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            ListNode *ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    
    return nullptr;
}