Amazon Interview Question: To find and return the common... | Glassdoor

Interview Question

Software Development Engineer Intern Interview Seattle, WA

To find and return the common node of two linked lists

  merged into a 'Y' shape.

Interview Answer

13 Answers


how did the two linked lists make their poses to merge into a 'Y' shape, one's head attached to the waist? please explain more to help understand the question

appenthused on Feb 17, 2012

The two linked lists were something like: 1->2->3->4->5 and 3->4->5->6->7->8.

djdj on Feb 17, 2012

For a Y shaped like this: 1 -> 2 -> 3 -> 4 ->7 -> 8 -> 9
5 -> 6 -> 7 -> 8 -> 9 where the trunk portion is of constant length, it is easy. Get the length of the first list. In our case 7. Get the length of the second list: 5. Difference is 2. This has to come from the legs. So, walk the difference in the larger list. Now node1 points to 3. node 2 points to 5. Now, walk through the two lists until the next pointers are the same.

kvr on Feb 18, 2012

@kvr what if the lists are 1-2-3-4-7-8-9 and 12-13-14-5-6-8-9

snv on Feb 22, 2012

Can this be done using hash tables? Or is there anything more efficient?

Anonymous on Feb 25, 2012

i think that kvr's answer is the best.
@snv if the two lists are linked by the very last two nodes, then you would find out after you are checking the values of the second two last two nodes. you just got unlucky and basically have to check until the very end. so basically, as a diagram with your example, it would look like this

1 -2 -3 -4-7-8-9
 x -x -x -x -x-o

(sorry about spacing) but because you know the difference in length is 0, you can start comparing the two lists of nodes one by one. from the very beginning.

pc on Feb 26, 2012

HASH TABLE seems the only efficient wt.

1. add each element's address (of the smallest list)and push it to the hash table.
2. start walking second list.
3. get element compar eits address with hash table if match is found in hash table, return
4. if list is not exhausted, go to step 2.
5. return NULL

maddy on Apr 6, 2012

Hashtable is complete overkill. The point is to realize that the two linked lists have the same tail. That means if you traverse them with the same index but from the right you will eventually find the first similar node. It's almost as easy if the problem said the two linked lists had the same prefix, find the first node on which they split. Here you walk them with the same index from the left.

Pavel on May 25, 2012

First reverse both list and find point where both gets diverged

Akash on Feb 2, 2015

For Y condition the list could be
List 1: 1->2->3->4->5->6
List 2: 7->8->9->4->5->6
So reverse list would be
now compare two list and move forward
the position where you find next node of both are different is the point of merging

Akash on Feb 2, 2015

Some of the above will work for doubly linked list. If not, travel node by node simultaneously from each end. When one traversal ends and the postion of cursor at the traversal is the answer

Anonymous on May 3, 2015

kvr's answer is good but I think it could be optimized better by using 2 stacks. Traverse both lists putting each value into 2 separate stacks. Then when both are fully traversed, the head of each stack will match. Pop one off each at a time till they don't match, return the last popped. But I suppose it comes down to where the first match is at. If its the beginning of the list, kvr's answer will be better, if its at the end or bottom half 2 stacks would be better.

Anonymous on Jun 17, 2015

Let's say L1 is the list starting with the lower number, and L2 is the other

Set X = Head of L1
Set Y = Head of L2

While X <= Y
     Set X = Next(L1)
End While

If (X==Y)
    Return X
    While Y<=X
        Set Y = Next(L2)
    End While

    If X==Y
       Return X
    End If
End If

Repeat until you reach the end of either list.

Intrepid Fox on Sep 11, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.