## Microsoft Interview Question

• 0

Country: India

Comment hidden because of low score. Click to expand.
13
of 13 vote

Well, there are several approaches to solve this problem.

Note that i am only discussing the approaches[corner cases may need to be handled separately] starting from brute force to the best one.
Considering N: number of nodes in first linked list
M: number of nodes in second linked list

Approach 1:
Compare each node of first linked list with every other node of second list. Stop when you find a matching node, this is the merging point.

``````while(head1)
{
while(cur2)
{
return cur2;
cur2=cur2->next;
}
}``````

Time Complexity: O(N*M)
Space Complexity: O(1)

Approach 2:
Maintain two stacks. Push all the nodes of he first linked list to first stack. Repeat he same for second linked list.
Start popping nodes from both the stacks until both popped nodes do not match. The last matching node is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N+M)

Approach 3:
Make use of hash table. Insert all the nodes of the first linked list into hash.
Search for the first matching node of he second list in the hash.
This is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N)
Note that the space complexity may vary depending upon the hash function used[talking about C where you are supposed to implement your own hash function].

Approach 4:
Insert all the nodes of first linked list[by nodes, i mean addresses] into an array.
Sort the array with some stable sorting algorithm in O(N logN) time[Merge sort would be better].
Now search for the first matching node from the second linked list.
Time Complexity: O(N logN)
Space Complexity: O(N)
Note that this approach may be better than Approach 3 [in terms of space]as it doesn't use a hash.

Approach 5:
1. Take an array of size M+N.
2. Insert each node from the first linked list, followed by inserting each node from the second linked list.
3. Search for the first repeating element[can be found in one scan in O(M+N) time].
Time Complexity: O(N+M)
Space Complexity: O(N+M)

Approach 6: [A better approach]
1. Modify the first linked list & make it circular.
2. Now starting from the head of the second linked list, find the start of the loop using Floyd- Warshall cycle detection algorithm.
3. Remove the loop[can be easily removed as we know the last node].
Time Complexity: O(N+M)
Space Complexity: O(1)

Approach 7: [Probably the best one]
1. Count the number of nodes in first linked list[say c1].
2. Count the number of nodes in second linked list[say c2].
3. Find the difference[Lets say c1>c2] diff=c1-c2.
4. Take two pointers p1 & p2, p1 pointing to the head of the first linked list & p2 pointing to the head of the second linked list.
5. Move p1 diff times.
6. Move both p1 & p2 each node at a time until both point to the same node.
7. p1 or p2 indicates the merging point.
Time Complexity: O(N+M)
Space Complexity: O(1)

Comment hidden because of low score. Click to expand.
0

To add one more approach, reverse both the linked list ... then last matching node will give the node position. Similar to Stack approach , but this way we can save space.

In my view Hash approach is the best because there we are traversing the lists only once.

Comment hidden because of low score. Click to expand.
2
of 4 vote

1.) travel both the link lists and find out their length... (since after they merge the length would be same from point of merging ....)

so if both the lengths are same then traverse through both the lists one node at a time and go on comparing them....
if lengths are different then calculate the difference abs(length of A - length of B)

--- suppose the difference in length is X...

then travel X nodes in the longer linked list first....

and now travel 1 node at a time from both the list .... for shorter list from the starting and for longer list from the point after X nodes...

if the list is merging then you would get the point of merge

Time complexity O(n)

Comment hidden because of low score. Click to expand.
0

consider list 1: 1 ->2->7->8->9

list 2: 3->4->7->8->9

their length are same but the point of merging is not first node...

Comment hidden because of low score. Click to expand.
0

This is the right approach!

Just when lengths are equal you need to check for both first and last nodes!

Comment hidden because of low score. Click to expand.
0

@cobra : yeah thanks for pointing that out....
the statement went down the wrong way...
have editted it in the main post...

Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is the simple way of doing this
1. Find out lengths of both lists(Say List A and List B). This can be done in O(n)
2. Say lengths are a and b where a>b Now for for the bigger list traverse the node to next for (a-b). That if a is 10 and b is 8, Go to next node for List A twice,
3. Now start comparing the nodes one by one, when they are equal it is the merge point

So overall complexity is O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 2 vote

1. If list merge then last node of both list will be same
2. Now from last node, traverse both list in reverse and get the merge point

Comment hidden because of low score. Click to expand.
0

How would you travel in reverse direction ???

Comment hidden because of low score. Click to expand.
0
of 0 vote

Keep moving both the pointers to next and check if they point to same address, if so then we get the merge point, if either of the pointers become null then we do not have any merge point between the two linked lists.

while(1)
{
if(p1 == null || p2 null) return null;
if(p1 == p2) return p1;
p1=p1->next;
p2=p2->next;

}

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

List data structure doesnt contain 'isVisited' variable.. you cant modify the data structure elements given..

For a node, there can be only 'value' and pointer to the next node

Comment hidden because of low score. Click to expand.
0

That's why I stated if I could change here

Am I allowed to change Node "Value" instead??

Comment hidden because of low score. Click to expand.
0

you can change the value of the node but how will you arrive at the solution?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.