Goldman Sachs Interview Question

How to identify intersection point of two LinkedList?

Interview Answer

Anonymous

Jan 14, 2016

If the length of the two linked lists is the same, the intersection can be found by simply traversing the two node by node, comparing each node physically - if the nodes are equivalent that is the intersection. Assuming there is no cycle in the linked list, one can simply determine the length of the two linked lists, and cut the front off of the longer one. If there is a cycle, a trick can be used to determine a 'sudo-length' for the two. Traverse the linked lists normally and 2 nodes at a time, comparing the current node for each at each iteration. If the nodes are ever physically equivalent there is a cycle and you can use this point as the sudo-end of the linked lists (it might not actually be the end but will be suitable for determining a consistent length for the two lists.