Unofficial C Solution to Problem 2.6 in Cracking the Coding Interview (5th Edition)

10 May

There is a follow up question: how to determine whether two linked lists, to say list1 and list2, intersect each other. Two solutions are available for this problem.

On one hand, we could link the end of list1 to the beginning of list2. Then this question turns to be the same as the original problem.

On the other hand, we can travel these two lists, get their length, and get their last nodes. If the last nodes are actually one node, these two lists intersect. If they intersect, we move the longer list, to safely assume it is list1, with len(list1)-len(list2) steps. Then iteratively in each round, two lists move one step, and compare their current nodes. The first same node is the intersection point of these two lists. (Here the same means they are essentially one node.)

Leave a Reply

Your email address will not be published. Required fields are marked *