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

Question

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

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 2

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 3

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 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

View more solutions

Comments

[rplusg]

merge means from that point there will be only one list.

[Artelius]

is modification of the list allowed?

[rplusg]

twitpic.com/m8eqo see this for more idea abt problem, and modification not allowed

[Kyle Rosendo]

From the picture you can use what I posted below.

[Stefan]

I'm pretty sure it doesn't work without modification of the list. (Or just copying it somewhere else to avoid the restriction to parse it only once.)

[Kyle Rosendo]

Might have been the point. Damn interviewers! Hehe

[cutiko]

I have an interesting proposal... assuming the common tail of the list is infinitely long. How can you find the node intersection using constant memory?

[Pavel Radzivilovsky]

posted below a solution without list modification, counters or more than O(N) iterations

[Eli Borodach]

I see by the answers that there is an assumption that there is no loop in the lists. Is that what you meant? What happens if there is a loop?

[greybeard]

@EliBorodach: If there was a loop in a singly linked list, it would be the tail. If two lists merged, they'd share this tail and would be of infinite length. (They wouldn't need to share a head as they could enter the cycle at different nodes.)

[jpgerek]

An example in golang O(n^2) and O(n) in time complexity, last one using a set: play.golang.org/p/XpK3D_p-oq

[Kyle Rosendo]

Pretty much what I said, just with fancier names. :P

[Kyle Rosendo]

Well changes slightly from what I wanted to say at first, but from what the OP seems to want, this will do the trick.

[Artelius]

It's clearer now. But linear in memory use. I don't like that.

[Kyle Rosendo]

The question didn't ask for more, otherwise the entire process can be multithreaded. This is still a simplistic "top level" view of the solution, the code can be implemented any number of ways. :)

[Kyle Rosendo]

However, you destroy the list in the process, never to be used again :P

[Artelius]

Not at all. This solution is O(n) in operations and O(1) in memory usage (in fact only requires two pointer variables).

[Kyle Rosendo]

Yea, should have deleted my prior comment as my solution changed a bit. Hehe.

[Artelius]

Uh, what? Multithreading is a way of better utilising processing power, not reducing the total processing power an algorithm requires. And saying the code can be implemented in any number of ways is just an excuse.

[Kyle Rosendo]

Nod, was getting excitable and didn't read it correctly. Slap on the wrists warranted.

[Artelius]

But I don't see how that was applicable in the first place?

[P Shved]

@Kyle Rozendo , well, my solution changes lists in the way they can be restored after processing. But this is more clear demonstration of the concept

[Kyle Rosendo]

Your explanation did, not the algorithm itself. Perhaps I view it differently, but hey.

[Artelius]

You probably do. But that's OK.

[Skizz]

This really bends the 'parse each list only once' to near breaking point. All you're doing is copying one list and then checking the other list against the copy.

[tster]

I didn't see that modification of the list was not allowed. I'll give it a think, but nothing is coming to mind without storing every node seen.

[Skizz]

Comment to question states modification of list not allowed!

[P Shved]

C'mon, that's the correct answer! We just need to adjust the question :)

[Stefan]

That's the equivalent of processing a list twice.

[Kyle Rosendo]

Well, yes and no. I'm not copying the list itself, simply the references. So at least the overhead isn't exactly the same, kinda :P

[tster]

I like this answer (very creative). The only problem I have with it is that it assumes you know the length of both lists.

[Skizz]

I suppose that, technically, you're doing stuff with the lists twice, but it's a significant improvement on Kyle Rozendo's solution. Now, if 'processing the list' is defined as 'reading the link value and following the pointer' it could be argued that it does process the list once - it reads each link value once, stores it and then compares them.

[rplusg]

you cannot modify list, and we don't know the length--these are the constraints...any how, thanks for a creative answer.

[P Shved]

@tster , @calvin , the answer doesn't assume, we need the length. It can be calculated inline. Adding explanations to my answers.

[Kyle Rosendo]

Is definitely going to be faster than mine, no doubt.

[keshav84]

+1 like this and also doesnt need any modification to the list, also most of the linked-list implementations usually provide for length

[Raulp]

I have two questions here : (1) Why the the list which reaches merge point later will go towards the beginning of the first list (2) The question says you should parse the list once only but you are traversing it twice , one forward and then reverse.

[Karoly Horvath]

Excellent algorithm to create memory leaks.

[jman]

+1, this is what naturally comes to mind with "iterate only once" dunno why this never got up voted! Beautiful solution.

[Forethinker]

@Raulp: 1) because the first iterator flipped the pointer 2) Yup. That is not a question.

[Forethinker]

If you choose to modify the list, why not mark them as 'seen' with some data member as you go along? There is no restriction that there is a empty data member waiting to be used. :) It can use some hash function for the marker value so that an iterator knows which node has been seen already by the other iterator and marked with valid mark. That is modifying the node, not the list (i.e. pointers). O(n) solution.

[P Shved]

@Forethinker hashing visited nodes and/or marking them as seen requires O(list length) memory, while many solutions (including mine, however imperfect and complicated it is) require O(1) memory.

[Cong Hui]

enlightened by such neat answer

[Cong Hui]

that's just brilliant!

[Rohit]

What if we have cycle in the merged part?

[tster]

This is a good answer, but you have to go through the lists twice which violates condition #2.

[Tuxdude]

By opposite list, do you mean traversing the pointers of the same list in the opposite direction, or in other words the prev pointer of a doubly linked list ?

[Pavel Radzivilovsky]

We have too many Pavels. My solution does not require modifying the list.

[Flami]

Logically it looks correct but as soon as pointer reaches end of one list and if we point to start of second list, it will form a loop in the list. I tried this solution, but didn't work.

[Yakov Galka]

@Flami: You don't modify the lists, only the pointers. I.e. to advance p2: p2 = p2->next ? p2->next : head1; and vice versa.

[ChrisG]

It does take 2 traverses at maximum. The two pointers will meet after 0 or 2 traverses of each linked list, and the answer lies in the difference of the lengths of the two lists. I think it's better that Pavel's answer above because in the case where the two lists are of the same length there is no need to traverse the two lists more that once, where in Pavel's it always requires two traverses. Should be the accepted answer!

[Pavel Radzivilovsky]

@ChrisG this is not true; in my solution, only one pass for equal lists.

[ChrisG]

Well I know. That's what I said. When the two linked lists are equal your solution works before a whole traverse of any of the two lists is completed (hence the 0 traverses). I misspelled a than. I wanted to say "I think it's better that Pavel's answer above " and that must have led to the confusion.

[alternated direction]

I find this solution quite elegant, if a merge point is guaranteed to be present. It will not work to detect merge points, as if one is not present it will loop infinitely.

[pslayer89]

I think an additional step might work with this solution which would be to iterate the two lists to their ends and checking if they share the common last node. After that we can iterate the pointers to find out the merging node.

[syockit]

This pretty much iterates one of the lists more than once, though in form of an array instead of the list itself.

[NoamG]

@PavelRadzivilovsky I'm missing something or there's a bug. If the 2 lists have different size it looks not good: A-->B-->C | V 1-->2-->3-->4-->5

[Pavel Radzivilovsky]

@NoamG, check again for lists of different size. You will see that the pointers meet at the merging point on the second pass.

[greybeard]

While this looks good, Artelius gave this answer 2009/10/20.

[greybeard]

1. not only modifies but destructs the first list. 2. is suggested time and again.

[greybeard]

I'm afraid (because of Ω(n) additional space) this is the only approach (not sort of rebuilding the list(s) and) not parsing a list more than once. Detecting a loop in the list is trivial for the first list (check if node in set) - use any loop detection method on the second list to ensure termination. (The interview question may have been about listening carefully to a problem statement, and not jumping in to use a hammer you happen to know to hit something not quite a nail.)

[greybeard]

But for the error handling cycles, this looks very much like isyi's answer.

[greybeard]

(I liked the list with each item starting a line better. Consider using a spelling checker.)

[Nikolai Golub]

That's super brilliant! Explanation: we have 2 lists: a-b-c-x-y-z and p-q-x-y-z. path of first pointer a,b,c,x,y,z,p,q,x, path of second pointer p,q,x,y,z,a,b,c,x

[Vihaan Verma]

Good answer. What will the time complexity for this though. 0(n + m) ? where n = nodes in list 1 , m = nodes in list 2 ?

[Chetya]

This works only if you know that the 2 lists merge before hand.

[rghome]

You need to add some explanation to your answer. Code only answers may get deleted.

[RDM]

Amongst all other brilliant solutions, this is by far the most simplest to understand and implement. Voted +1 and I wish this could be proposed as the solution to the OP's question.

[Vishal Anand]

instead of moving both of the pointers in both list: we can just see if the diff >= small of two path, if yes, then move in small list by small value else move in small list by diff + 1 value; if diff is 0 then last node is the answer.

[Ritwik]

This solution works because... Suppose two linked list are L1 of size n and L2 of size m. Intersection point (IP), which is neither head1 nor head2, lies after i hops from head1 and * j hops from head2 (draw it). Maintain 2 pointers, p1 = head1 and p2=head2. Then after n hops, p1 will be at head2 and p2 will be somewhere doesn't matter. Now, after j hops, p1 will be at the IP (why? because * ) and p2 would have completed n+j hops. The key part now is, to prove p2 will also be at IP.

[Ritwik]

It is evident that n-i = m-j (the common nodes between L1 and L2), or n+j = m+i. Putting this in previous comment. We get, p2 would have completed m+i hops. By tracing our steps, we know, after m hops p2 will be at head1. And after subsequent 'i` steps from head1 we will reach IP for sure (why? because IP lies after i hops from head1). Hence proved, now p2 will also be at IP.

[Ritwik]

However, this solution fails because... if IP (Intersection Point) is either head1 or head2. Then either i or j equals to zero. Then after n+j hops (or m+i hops), you'll land up in the same configuration as the initial one i.e. p1 will be at head1 and p2 will be at head2. This would result in an infinite loop. That is why, this is not an accepted answer.

[adev]

Brilliant. For those who didn't understand, count the number of nodes traveled from head1-> tail1 -> head2 -> intersection point and head2 -> tail2-> head1 -> intersection point. Both will be equal(Draw diff types of linked lists to verify this). Reason is both pointers have to travel same distances head1-> IP + head2->IP before reaching IP again. So by the time it reaches IP, both pointers will be equal and we have the merging point.

[rneha725]

brilliant solution!!

[Jordy Baylac]

this is awesome dude!

[LionsAd]

In fact this can even be used to calculate if there is a merge point as once the end of one list is reached we could just store the end node and compare once the other list reaches it end. As we only create a virtual cycle and not a real one, this works well.

[Ayxan Haqverdili]

This is the same logic as Floyd’s Cycle detection algorithm, right?

[mr NAE]

This solution is O(n^2) complexity. When size of list1 greater than n = size of list2 by 1 you have to do at least n*(n-1) iterations through the lists.

[greybeard]

In its original revision, this just spelled out the highest voted answer (Pavel Radzivilovsky, 2013).

[PKV]

Genius! Both the lists have end part common - starting from the merge point. When you see it graphically, see below. So, at most, the second iteration will give you the result. ``` [a a a a a a] - M - [c c c c c] - [b b b] - M - [c c c c c] [b b b] - M - [c c c c c] - [a a a a a a] - M - [c c c c c] ```

[Anh Nhat Tran]

It will fail for list 1: 1-2-3, list 2: 1-2-3. The merge point is 2 but you will never found it by comparing 2 pointers.

[Anh Nhat Tran]

@KarolyHorvath could you explain why it leads to memory leaks? I understood why it will destroy the list but what about memory leaks?

[Asif Iqbal]

While this algorithm is brilliant, I can't seem to find a way to check if the two lists merge at all or not. I mean, if the two lists don't merge, then this algorithm will run indefinitely, right?

[Jubayer Abdullah Joy]

The time complexity of this approach is O(n+m) where n and m represent the length of the linked lists. A marge point should be guaranteed else it would run indefinitely. This is because the required iteration is (head1->tail + head2-> margePoint) and (head2->tail + head1-> margePoint) which are the same size of maximum (n+m), worst case: only the last node is common.

[Amit Dube]

This is just a brute force approach comparing every single element of first list to every element of first list. that gives a time complexity of O(n*m).

[Mateen]

//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! // How this pointer go to the head of the other list?

[Mateen]

No. It there's no intersection that can also be detected. You just need to keep the state if these pointers reach the end of the linked list(s) more than one. It any pointer reaches the end more than onec there's no intersection for sure. See my implementation here: leetcode.com/submissions/detail/545521476