Best Possible algorithm to check if two linked lists are merging at any point? If so, where?

Question

Hello,

This is an interview question for which I don't have an answer. Given Two lists, You cannot change list and you dont know the length. Give best possible algorithm to:

1. Check if two lists are merging at any point?
2. If merging, at what point they are merging?
3. If I allow you to change the list how would you modify your algorithm?

Answer 1

Number 1: Just iterate both and then check if they end with the same element. Thats O(n) and it cant be beaten (as it might possibly be the last element that is common, and getting there always takes O(n)).

Answer 2

1. Walk those two lists parallel by one element, add each element to Set of visited nodes (can be hash map, or simple set, you only need to check if you visited that node before). At each step check if you visited that node (if yes, then it's merging point), and add it to set of nodes if you visit it first time. Another version (as pointed by @reinier) is to walk only first list, store its nodes in Set and then only check second list against that Set. First approach is faster when your lists merge early, as you don't need to store all nodes from first list. Second is better at worst case, where both list don't merge at all, since it didn't store nodes from second list in Set
2. see 1.
3. Instead of Set, you can try to mark each node, but if you cannot modify structure, then it's not so helpful. You could also try unlink each visited node and link it to some guard node (which you check at each step if you encountered it while traversing). It saves memory for Set if list is long enough.

Answer 3

See this old question

Answer 4

I'm assuming that we are talking about simple linked lists and we can safely create a hash table of the list element pointers.

Q1: Iterate to end of both lists, If the respective last elements are the same, the lists merge at some point.

Complexity - O(N), space complexity - O(1)

Q2:

1. Put all elements of one list into a hash table
2. Iterate over 2nd list, probing the hash table for each element of the list. The first hit (if any) is the merge point, and we have the position in the 2nd list.
3. To get the position in the 1st list, iterate over the first list again looking for the element found in the previous step.

Time complexity - O(N). Space complexity - O(N)

Q3:

1. As Q1, but also reverse the direction of the list pointers.
2. Then iterate the reversed lists looking for the last common element - that is the merge point - and restoring the list to the original order.

Time complexity - O(N). Space complexity - O(1)