+1  A: 

Maybe I am over simplifying this, but simply iterate the smallest list and use the last nodes Link as the merging point?

So, where Data->Link->Link == NULL is the end point, giving Data->Link as the merging point (at the end of the list).

EDIT:

Okay, from the picture you posted, you parse the two lists, the smallest first. With the smallest list you can maintain the references to the following node. Now, when you parse the second list you do a comparison on the reference to find where Reference [i] is the reference at LinkedList[i]->Link. This will give the merge point. Time to explain with pictures (superimpose the values on the picture the OP).

You have a linked list (references shown below):

A->B->C->D->E

You have a second linked list:

1->2->

With the merged list, the references would then go as follows:

1->2->D->E->

Therefore, you map the first "smaller" list (as the merged list, which is what we are counting has a length of 4 and the main list 5)

Loop through the first list, maintain a reference of references.

The list will contain the following references Pointers { 1, 2, D, E }.

We now go through the second list:

-> A - Contains reference in Pointers? No, move on
-> B - Contains reference in Pointers? No, move on
-> C - Contains reference in Pointers? No, move on
-> D - Contains reference in Pointers? Yes, merge point found, break.

Sure, you maintain a new list of pointers, but thats not outside the specification. However the first list is parsed exactly once, and the second list will only be fully parsed if there is no merge point. Otherwise, it will end sooner (at the merge point).

Kyle Rozendo
Please donot over simplify.
calvin
Feel free to correct me? You did give me a chuckle though.
Kyle Rozendo
Well changes slightly from what I wanted to say at first, but from what the OP seems to want, this will do the trick.
Kyle Rozendo
It's clearer now. But linear in memory use. I don't like that.
Artelius
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 Rozendo
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.
Artelius
Nod, was getting excitable and didn't read it correctly. Slap on the wrists warranted.
Kyle Rozendo
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.
Skizz
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
Kyle Rozendo
A: 

Are you sure is the question correct?

Merging arrays or lists with O(n) complexity is a common question during interviews:

http://www.interviewpattern.com/post/Merging-Arrays-Interview-Question.aspx

First, I don't see any advantage of merging two lists and keeping memory of the merging point (unless you are interested in some sort of sorting). Merging means "go from two lists to one list only". Second, why shouldn't you just keep a pointer to the last element of the shortest list?

Roberto Aloi
Happy with the down vote. It would be nice to get an explanation together with it, though.
Roberto Aloi
+1  A: 

This arguably violates the "parse each list only once" condition, but implement the tortoise and hare algorithm (used to find the merge point and cycle length of a cyclic list) so you start at List A, and when you reach the NULL at the end you pretend it's a pointer to the beginning of list B, thus creating the appearance of a cyclic list. The algorithm will then tell you exactly how far down List A the merge is (the variable 'mu' according to the Wikipedia description).

Also, the "lambda" value tells you the length of list B, and if you want, you can work out the length of list A during the algorithm (when you redirect the NULL link).

Artelius
Pretty much what I said, just with fancier names. :P
Kyle Rozendo
Not at all. This solution is O(n) in operations and O(1) in memory usage (in fact only requires two pointer variables).
Artelius
Yea, should have deleted my prior comment as my solution changed a bit. Hehe.
Kyle Rozendo
But I don't see how that was applicable in the first place?
Artelius
Your explanation did, not the algorithm itself. Perhaps I view it differently, but hey.
Kyle Rozendo
You probably do. But that's OK.
Artelius
+1  A: 

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.

tster
However, you destroy the list in the process, never to be used again :P
Kyle Rozendo
@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
Pavel Shved
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.
tster
C'mon, that's the correct answer! We just need to adjust the question :)
Pavel Shved
+7  A: 

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.

Pavel Shved
Comment to question states modification of list not allowed!
Skizz
I like this answer (very creative). The only problem I have with it is that it assumes you know the length of both lists.
tster
you cannot modify list, and we don't know the length--these are the constraints...any how, thanks for a creative answer.
calvin
@tster , @calvin , the answer doesn't assume, we need the length. It can be calculated inline. Adding explanations to my answers.
Pavel Shved
A very neat solution.
Nick Johnson
A: 

Here's a solution, computationally quick (iterates each list once) but uses a lot of memory:

for each item in list a
  push pointer to item onto stack_a

for each item in list b
  push pointer to item onto stack_b

while (stack_a top == stack_b top) // where top is the item to be popped next
  pop stack_a
  pop stack_b

// values at the top of each stack are the items prior to the merged item

Skizz

Skizz
That's the equivalent of processing a list twice.
Georg
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.
Skizz
Is definitely going to be faster than mine, no doubt.
Kyle Rozendo
A: 

I have tested a merge case on my FC9 x86_64, and print every node address as shown below:

Head A 0x7fffb2f3c4b0
0x214f010
0x214f030
0x214f050
0x214f070
0x214f090
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170


Head B 0x7fffb2f3c4a0
0x214f0b0
0x214f0d0
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170

Note becase I had aligned the node structure, so when malloc() a node, the address is aligned w/ 16 bytes, see the least 4 bits. The least bits are 0s, i.e., 0x0 or 000b. So if your are in the same special case (aligned node address) too, you can use these least 4 bits. For example when travel both lists from head to tail, set 1 or 2 of the 4 bits of the visiting node address, that is, set a flag;

next_node = node->next;
node = (struct node*)((unsigned long)node | 0x1UL);

Note above flags won't affect the real node address but only your SAVED node pointer value.

Once found somebody had set the flag bit(s), then the first found node should be the merge point. after done, you'd restore the node address by clear the flag bits you had set. while an important thing is that you should be careful when iterate (e.g. node = node->next) to do clean. remember you had set flag bits, so do this way

real_node = (struct node*)((unsigned long)node) & ~0x1UL);
real_node = real_node->next;
node = real_node;

Because this proposal will restore the modified node addresses, it could be considered as "no modification".

EffoStaff Effo
+6  A: 

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.

Artelius
Today, when we were drinking vodka, I proposed this question to a friend of mine, and he gave away the same answer as yours and asked to post it on SO. But you seem to be first. So I'll make a +1 for you from me and I wish i could do another +1.
Pavel Shved
+1 like this and also doesnt need any modification to the list, also most of the linked-list implementations usually provide for length
keshav.veerapaneni
A: 

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
rachvela
I already suggested this method.
Artelius