Linked list cycle II (Update)

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

This question looks more like a mathematical competition question than a algorithm problem. Discrete math is not in my favorite toolset so figuring out a good way to solve this problem took me a long time.

Algorithm worse than O(n) is trival. Solving it in O(n) time is when it get interesting. The question itself can be divided into two parts:

1. Detect whether there is a cycle in the singly linked list.
2. If there is a cycle, where does this cycle starts.

To answer question 1, think of the turtle and the rabbit, if the rabbit is fast enough, and there is loop in the linked list, rabbit can revisit turtle again. 

The second question is tricky. Suppose in question 1, turtle has speed of 1 and rabbit has speed of 2. When turtle and rabbit meet each other, turtle has visited k node, rabbit has visited 2k node. Suppose the existing cycle has perimeter of r, and rabbit has run n more loops than turtle, we can come up with an easy equation:

2k-k=n*r

Suppose the linked list has the following structure:

where non-cycle part has length s, turtle path k=s+m . Now we can come up with this:

                          2n*r = s+m+n*r

=>                        n*r = s+m

=>                        (s+m)%r = 0

Now it gets tricky. You can easily find n is not a number that we can calculate.

Other posts claim we can set n = 1, so we can have s = r-m, which means if a turtle starts at the original starting point, another turtle starts at the rendezvous point, when they meet, you will find the starting point of the circle.

I think we can think it like this, If we let the rabbit run one more loop, this relative position will not change. so now it is easy to see r = m+s based on:

[(n+1)*r} % r = (s+m)%r = 0

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // special cases
        if(!head || !head->next) return NULL;
        if(!head->next->next) return NULL;
        if(head->next->next == head) return head;
        // now linked list has at least 3 nodes
        
        // ready? set
        int tortoiseTravelled = 1;
        ListNode* tortoise = head->next;
        ListNode* rabbit = head->next->next;
        
        // go!
        while(rabbit && rabbit->next && rabbit!=tortoise) {
            rabbit = rabbit->next->next;
            tortoise = tortoise->next;
            ++tortoiseTravelled;
        }
        
        if(!rabbit || !rabbit->next) return NULL;
        // now we found a cycle. Starting from current location,
        // let's find the starting point of loop.
        ListNode* surveyer = rabbit;
        
        ListNode* surveyer2 = head;
        while(surveyer != surveyer2) {
            surveyer2 = surveyer2->next;
            surveyer = surveyer->next;
        }
        
        return surveyer;
    }
};

Followup (From link):

The followup questions extend one linked list to two linked lists. Questions are:

1. How to determine whether two acyclic singly linked lists have crossed section.
2. If we don't know whether those two singly linked lists are acyclic or not, how to determine whether they have crossed section.
3. In case 2, if those two linked lists have crossed section, how to find the starting node of the crossed section.

For question 1: 

Think about crossed section. Singly linked list can only have crossed section like this:

It is impossible for list 1 and list 2 to separate after they cross each other. Thus:

1. A natural way to solve question 1 is to check whether list 1's ending node is the same as list 2's ending node.
2. Or connect list 1's starting node to list 2's ending node, manually constructing a loop if list 1 and list 2 cross each other. If a loop is constructed then list 1 and list 2 do have cross section.
   

For question 2. 

The difference between question 1 and 2 is whether linked list 1 or 2 has loop or not. Divide this into 3(2) cases.

1. List 1 has loop but list 2 does not have loop. 
2. List 1 and 2 all have loop.

Bear in mind that we are handling a singly linked list. Having loop in only one list means these two lists cannot have cross section. If a cross section is found, then they will all be trapped in the loop. Case 1 means list 1 and 2 does not have cross section. Check the previous section for "checking whether a linked list has loop".

For case 2, we only need to make sure they have same loop. Find a loop node in list 1 as A and loop node in list 2 as B, check whether we can reach B from A. Problem solved.

For question 3. 

This one is tricky. Since we don't know whether they have loop or not. We only know they have cross section. Divide this into 2 cases.

1. They don't have loop.
2. They all have loops.

Case 1 can be solved just as what we did in linked list cycle II. We manually construct a loop and find the starting point of the loop. Problem solved.

Case 2 Type 1. When lists enter the loop, they have the same entry point.

Since we already know a loop exists for both list 1 and list 2, and all the nodes after rendezvous point pt are common nodes, if we can figure out list length of list 1 and list 2, we can easily get to rendezvous point using two pointers from list 1's head and list 2's head.

Suppose list 1 is longer with length(list1) and list 2 is shorter with length(list2), if list 1 pointer starts first (to compensate list length difference), after list 1 pointer travels length(list1) - length(list2) nodes, start another pointer from list 2, when these two pointer converge, we find point pt. This strategy can be applied to case 1 too.

Now the question goes back to how to determine list length given the list has a loop. Back to the first figure, we want to know s+(r-m)+m = s+r. s is what we calculated in the original leetcode problem, r can be achieved during s calculation. Problem solved.

Case 2 Type 2. When lists enter the loop, they have different entry points.

Why this case is different from Case 2 Type 1? Given linked list 1: {a,b,c,d,b,c,d,...} and {e,c,d,b,c,d,b,...}, they all have length 4. Use case 2 type 1 strategy we will get caught in a dead loop. Why this happens? Case 2 Type 1 will work only if from rendezvous point pt to entry point e exists for both list 1 and list 2. Thus when length difference is compensated they will travel in the loop side by side. For type 2, without pt->e part, they will never rendezvous, causing a big difference.

The strategy is still simple. We only need to first confirm we are in this case 2 type 2, then find out list 1's entry point e1, list 2's entry point e2. Problem solved.