Microsoft Interview Question Software Engineer in Tests
Country: United States
Interview Type: In-Person
This is simple, and I believe it was answered before.
If the 2 lists merge, this means they have at least one common node.
The algo is simple, as follows:
say listA is size N and listB is size M (in example above N=4 and M=6).
Now, skip the first M-N elements from the longer list (in our case it's 2).
Then start comparing node by node, basically compare first element in listA with third element of listB. If it's same node, voila, you found the result, otherwise move to next item in both lists and compare them (in our example next will be second element in listA and fourth element in listB).
assume if list is
A->B->C->D
and second one be
A->B->C->D->E->F
now if I am getting it right what you would do is you will compare the first element A with C of second list and continue and we will never find the same A->B->C->D in second list..
Am i getting your solution wrong ?
@aayush
are the examples you have quoted, merge lists. Those two nodes are merge lists.
( Find the merge node of two linked lists where the rest of the nodes are same? is it correct meaning of the question, sorry if i am wrong)
@amustea, The assumption you made is both lists are unique. Is it a correct assumption. what if the lists are
A->B->C->D->C->D->E and
C->D->E
I must be missing something.
I see this question no different than asking - Find a node in a linked list.
The node to be found is head node of the smaller list.
The trick is that - there may be more than one A (head nodes) - and hence the comparison-traversal of the smaller linkedlist will be required to declare its a merge point.
count nodes of both the list , say it be x & y. deduct the lesser from higher one say it be "N".
- Anonymous February 28, 2012Now in the longer link list traverse N nodes.
Now start moving both the list one node at a time and compare. you will get the joint.