Production code for finding junction in a linked list

Question

Hi all,
I was asked this question in some interview.

I was required to write code for finding junction in a linked list (which is in form of Y with both arms not necessarily equal) for production environment in O(1) space and linear time.
I came up with this solution (which i had previously seen somewhere) :

1. Measure lengths of both lists, let them be l1 and l2 
2. Move the pointer of larger list by |(l1-l2)|.
3. Now move together both the pointers, if they point to same location,
that is the junction.

Interviewer: How will your code handle ?

Case 1. The Y-format linked list has loop in the end after the junction.
Case 2. Either of the input lists is cyclic and they don't merge.
Case 3. The Y-format list has loop in the end before the junction.

In response to case 1, my answer was:

I will find the loop in the list using two pointers (one fast and slow), measure the length to the node at which both the pointers meet and then proceed as previous case.

Whereas, for cases 2 and 3, I was able to figure out no better solution than gracefully exiting when a loop is detected (using the 2-pointer technique).

I believe there are better answers to this problem.Please drop down yours :).

Thanks,

Answer 1

The problem is made difficult by the interviewer's (seeming) interpretation that the following shapes are also considered valid:

A\  _____     A\              ___
  \/     \      \            /   \
   \     /       \           \   /
    +---'         +-------------'
   / P           / P
  /             /
B/            B/

i.e. there is a junction but then the list loops back to a place either before or after the junction. The procedure of calculating the length of the list does not help directly because the length of a cyclic list is not defined.

First note that the length of a loop at end of a cyclic list can be calculated by this O(1) memory / O(n) time procedure:

int loop_length(List *n) {
  Node *hare = n, *tortoise = n;
  int phase = 0, cnt = 0;
  while (true) {
    hare=hare->next; hare=hare->next; tortoise=tortoise->next;
    if (hare==tortoise) phase++; 
    if (phase==1) cnt++;
    if (phase==2) return cnt;
  }
}

For example, consider the cyclic list

(1)-->(2)-->(3)-->(4)
             |     |
            (6)<--(5)

The algorithm works as follows (T=tortoise, H=hare):

       /--------\
 1--2--3--4--5--6    phase  cnt
 HT                  0      0
    T  H             0      0
       T     H       0      0
          HT         1      1
             T  H    1      2
           H    T    1      3
       T        H    1      4
          HT         2      4 : TERMINATED, cnt=4

Now if there are X nodes before the node that forms the junction point for the cycle (in the example node (3)), i.e. X=2, and the cycle consists of C nodes (in the example C=4), when the tortoise enters the junction point for the first time after X steps the hare is in the cycle at location (2X - X) % C, i.e. (X % C) (in the example, tortoise enters (3) after 2 steps 3nd hare is then at location L = (2 % 4 = 2), i.e. in node (5) (the index is zero-based). It will now take (C-L-1) steps for the hare to reach the tortoise (1 step in the example) as the hare has an 'advantage' of L steps; this means that the number of steps for the algorithm until the hare meets the tortoise the first time is

  X + (C - X % C - 1)     ; in the example 2 + (4 - 2 - 1) = 3

C is known (it's calculated by the algorithm), and the total number of steps (denote by S) can be calculated, i.e. we have

  S + 1 - C = X - X % C

Suppose now that the hare as an extra advantage of Q steps, i.e. hare takes first Q next pointers forwards before the algorithm starts; then when the tortoise enters the junction point the hare is at location ((X + Q) % C), and we get

  S + 1 - C = X - (X + Q) % C

This gives now a procedure to calculate the difference in the length of the paths from 'A' and 'B' to the common junction point P (denote the lengths a and b and their difference thus a-b) (assume a > b without loss of generality).

First run the algorithm from starting point A, calculate cycle length C and store number of steps S_A. Then run it so that the tortoise starts at A and the hare at B and calculate the number of steps S_X. This means that the hare has now an advantage of (a-b) nodes, i.e.

  S_X + 1 - C = a - (a + (a - b)) % C = a - (2a - b) % C

Thus

  S - S_X == (a - b)   modulo   C

I.e. the difference gives the length difference modulo C; to calculate the length difference's quotient by C run the algorithm usually from starting point B, getting number of steps S_B, i.e. all together

  S_A + 1 - C = a - a % C
  S_B + 1 - C = b - b % C
  S_X - S_A == (a - b) % C

subtract the first two equations to get

  S_A - S_B = (a - b) + [-1 * (a % C) + b % C]

the term in square brackets is in ]-C,+C[ , so

  (S_A - S_B) - C < (a - b) < (S_A - S_B) + C

in this interval there are at most two differences which equal (S - S_X) modulo C; use them both to try to spot the junction point---problem solved.

Example:

 A(1)--(2)
        |
 B(3)--(4)--(5)--(6)
        \_________/

In the calculation of S_A, the hare and tortoise meet after 3 steps at (5) and cycle length 3 is returned. In the calculation of S_B, the hare and tortoise meet after 3 steps at (6) and cycle length 3 is returned. For S_X, hare enters at B and tortoise at A; they meet after 2 steps at (4). This gives

  0 - 3 < (a - b) < 0 + 3
  (3 - 2) == (a - b)  modulo  3

i.e. the length difference between (a - b) is 1 modulo 3; this gives possible length differences { -2, +1 }; -2 is disregarded by assumption a > b, so we get a = b + 1. Then the junction point is found by traversing first +1 node from A forwards to (2), and then advancing from both arms at the same pace until the junction point is found.

Integration with the cases where there are non-shared loops and/or no loops left as an exercise to the reader.