Thursday, June 30, 2011

Get the Intersection Points of Two Link List

Problem:  There are two link lists that have an intersection point (they have the same end), which makes them forms a "Y" shape. Find the intersection point.

Solution:  Definitely we can traverse one list and hash all the nodes. Then traverse the other list. But if we want a O(1) space complexity, we can try the following two methods:

  1. Traverse both lists to get the their length. Then move the pointer from the head of the longer list by len(long_list) - len(short_list) steps. Then move both pointers in parallel and compare.
  2. Traverse one list, make the last node point to the head to form a circle and remember the length l. Move one pointer l steps, starting from the head of the second list. Then also start to move a second pointer, still from the head of the second list. Two pointers move in parallel. The node they meet each other is the intersection point.

No comments:

Post a Comment