Check if two linked lists merge. If so, where?

This question may be old, but I couldn't think of an answer.

Say, there are two lists of different lengths, merging at a point; how do we know where the merging point is?

Conditions:

1. We don't know the length
2. We should parse each list only once.

Solution 1:

The following is by far the greatest of all I have seen - O(N), no counters. I got it during an interview to a candidate S.N. at VisionMap.

Make an interating pointer like this: it goes forward every time till the end, and then jumps to the beginning of the opposite list, and so on. Create two of these, pointing to two heads. Advance each of the pointers by 1 every time, until they meet. This will happen after either one or two passes.

I still use this question in the interviews - but to see how long it takes someone to understand why this solution works.

Solution 2:

Pavel's answer requires modification of the lists as well as iterating each list twice.

Here's a solution that only requires iterating each list twice (the first time to calculate their length; if the length is given you only need to iterate once).

The idea is to ignore the starting entries of the longer list (merge point can't be there), so that the two pointers are an equal distance from the end of the list. Then move them forwards until they merge.

lenA = count(listA) //iterates list A
lenB = count(listB) //iterates list B

ptrA = listA
ptrB = listB

//now we adjust either ptrA or ptrB so that they are equally far from the end
while(lenA > lenB):
    ptrA = ptrA->next
    lenA--
while(lenB > lenA):
    prtB = ptrB->next
    lenB--

while(ptrA != NULL):
    if (ptrA == ptrB):
        return ptrA //found merge point
    ptrA = ptrA->next
    ptrB = ptrB->next

This is asymptotically the same (linear time) as my other answer but probably has smaller constants, so is probably faster. But I think my other answer is cooler.

Solution 3:

If

• by "modification is not allowed" it was meant "you may change but in the end they should be restored", and
• we could iterate the lists exactly twice

the following algorithm would be the solution.

First, the numbers. Assume the first list is of length a+c and the second one is of length b+c, where c is the length of their common "tail" (after the mergepoint). Let's denote them as follows:

x = a+c
y = b+c

Since we don't know the length, we will calculate x and y without additional iterations; you'll see how.

Then, we iterate each list and reverse them while iterating! If both iterators reach the merge point at the same time, then we find it out by mere comparing. Otherwise, one pointer will reach the merge point before the other one.

After that, when the other iterator reaches the merge point, it won't proceed to the common tail. Instead will go back to the former beginning of the list that had reached merge-point before! So, before it reaches the end of the changed list (i.e. the former beginning of the other list), he will make a+b+1 iterations total. Let's call it z+1.

The pointer that reached the merge-point first, will keep iterating, until reaches the end of the list. The number of iterations it made should be calculated and is equal to x.

Then, this pointer iterates back and reverses the lists again. But now it won't go back to the beginning of the list it originally started from! Instead, it will go to the beginning of the other list! The number of iterations it made should be calculated and equal to y.

So we know the following numbers:

x = a+c
y = b+c
z = a+b

From which we determine that

a = (+x-y+z)/2
b = (-x+y+z)/2
c = (+x+y-z)/2

Which solves the problem.

Solution 4:

Well, if you know that they will merge:

Say you start with:

A-->B-->C
        |
        V
1-->2-->3-->4-->5

1) Go through the first list setting each next pointer to NULL.

Now you have:

A   B   C

1-->2-->3   4   5

2) Now go through the second list and wait until you see a NULL, that is your merge point.

If you can't be sure that they merge you can use a sentinel value for the pointer value, but that isn't as elegant.

Solution 5:

If we could iterate lists exactly twice, than I can provide method for determining merge point:

• iterate both lists and calculate lengths A and B
• calculate difference of lengths C = |A-B|;
• start iterating both list simultaneously, but make additional C steps on list which was greater
• this two pointers will meet each other in the merging point