Linked list interview question

Answer 1

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

Answer 2

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?

Answer 3

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

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

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

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.

Answer 9

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