Question d’entretien chez Microsoft
You have two intersecting linked lists. Describe a function that returns a pointer to the node where they intersect.
Réponses aux questions d'entretien
Utilisateur anonyme
15 mai 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