Microsoft Interview Question: You have two linked lists tha... | Glassdoor

Interview Question

Software Development Engineer II Interview Redmond, WA

You have two linked lists that merge at some node. The

  lists could be billions of nodes long. Find the node where the lists merge in the most optimal time while using a low amount of memory.

Interview Answer

5 Answers


If the lists have a length value, then you should be able to do this pretty simply.

If two lists merge, then they have the same terminal node. That means that from the merge node to the end they have the same length. So if you subtract the smaller lists length from the larger you end up with a great starting point to begin searching. you then increment down the lists from that point on to find the node where both lists meet.

Scott on Sep 6, 2012

Above answer is not correct. Its a list so you can only start from the begininning.

If its a doubly linked list, yes, you can start at the end (and should), but you cannot start "mid-list".

Anonymous on Sep 13, 2012

I can think of two ways:
1) traverse from both heads, get two length: long, short
traverse again starting from Array1[long-short] and Array2[0], looking for the same pointer
O(4n) time, O(1) space

2) use a hash table holds all seen pointers. traverse from both heads
O(2n) time, O(n) space

Eric on Nov 2, 2012

Step 1: if the linked lists are not empty, find the length of each linked list. Since they have a common end point, we will get length of common area of the linked lists too.
Step 2: find the difference between the length of both list. Start traverse the biggest list till the difference in length between them, provided one of them is bigger than the other.
Step 3: now they are at the same remaining length. Traverse both of the together till both are pointing to the same next node.That node is the common node which is the merging point. If there is no such point, then they are not merged.

BVarghese on Aug 7, 2013

Suppose x nodes before merged node for List1, and y nodes before merged node for List 2, z shared nodes for two Lists.
List1.Length = x + z
List2.Length = y + z
Traverse List1, List2 to get their lengths.
List1.Length - List2.Length = x - y

Starting traverse at same time from (x-y+1)th nodes of List1, and head of List2 (when x>=y)
Starting traverse at same time from (y-x+1)th nodes of List2, and head of List1 (when x<=y)

till they point to the same node, that node is merged node. otherwise, no merged node

lol on Jun 17, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.