Microsoft Interview Question

You have two intersecting linked lists. Describe a function that returns a pointer to the node where they intersect.

Interview Answers

Anonymous

May 15, 2016

The key to the solution is to point out that if two lists intersect, from that point on they are one and the same and they end at the same node. 1) Measure both lists (E.g.: L1 is 13 and L2 is 10 - assume last 5 nodes in common) 2) Move long list ahead of L1 - L2, (E.g., move L1 to 3) 3) Now advance both lists at the same time and check each node 4) When you find the same node (i.e., data is the same) --> Return current node. (E.g., after moving both lists 5 positions ahead we encounter common node)

11

Anonymous

Sep 19, 2016

@Simon - great approach. Only thing we can't compare the data to determine whether both nodes are same. We have to compare the nodes by reference. That way we will make sure both nodes are identical. Hope this helps.

1

Anonymous

Mar 22, 2017

@Simon - are you sure it's gonna work when starting 5 nodes are common? I don't think so.