Linked List: Merged List Problem

Problem: There are 2 singly linked lists (list1 and list2) that merge at one of the nodes and share the nodes there onwards. The goal is to find the node where these linked lists merge or join.

Solution 1:

1. Find length of both linked lists, say len1 and len2.
2. Make current pointers for both lists equidistant from the common node. If one of the lists is longer we need to advance its current pointer by len1 - len2 (assuming list1 is longer). Now both current pointers should be equidistant from the common node. If both lists are same len, do nothing in step 2.
3. Traverse both lists simultaneously while comparing the current pointers for equality. At ant point if they are equal we have found the first common node. If we reach the end of the lists without find the common node then the lists do not overlap.

Solution 2 : This solution only tells if the lists are joined, not where though. Interesting technique nevertheless.

1. Update the tail of one of the lists to point to the head of the other.
2. Now use the linked list cycle/loop detection technique to find if there is a loop in the combined list.
3. If there is a loop then the list have node(s) in common, otherwise they don't.