First Common Node in Intersecting Linked Lists

You have two singly linked lists, L1 and L2, which start from different head nodes. Some number of nodes into each list, they meet at a common node and share all the nodes from that point on. Describe an algorithm for finding the first common node.

Solution

The naive approach would be to start with the first node of L1 and check each node of L2 to see if it matches, iterating until a match is found. But of course, we can do better.

The key is that because L1 and L2 have a common "tail", you can just compare corresponding nodes between L1 and L2, walking down the lists in tandem, as long as they are the same distance from the tail end of the list. To get to that point, you first traverse L1 and L2 separately to determine their lengths. Then you skip over the first |L1-L2| nodes from the longer list, since those couldn't possibly be part of the common tail. Now you're looking at the same number of remaining nodes in both lists. Just walk down them together, checking corresponding nodes until the common one is found.