Given two singly linked lists with both of them merging at some point. Find the position at which they merge. Eg: 1->30->50->65->2->59 88->46->65->2->59 The above two linked lists merge at 65. Find this node where they merge.. Question Courtesy: Antony(Friend) One possible Answer A simple answer would be to find the length of both the linked lists and have two pointers, one for each linked list. Move (difference in lengths) steps in the longer linked lists and then start moving both the pointers by one every time until you have both the pointers pointing to the same node. time Complexity - O(2n) = O(n)

Reply

Varlu, i do not believe this will always give you the correct solution or a solution at all. The only way your method would work is if you have a linked list that is sorted and you know how it is sorted. This way you know which pointer to increment and when. Otherwise, you may actually "skip" over the merge point you are trying to find in your method. There are a lot of ways to correctly do this but none will be O(n). The easy way is just have two nested loops and traverse one list checking each point against every point in the other list. If you find a value that is in the other list, check to see if they share the same next element until you hit the end of the list. This is worst case O(n^2).

Reply

Well, I think the answer depend on what are really these 'nodes'. If we consider them as objects holding the information on the next node - which forms the linkedlist - as well as their own data , then Varalu's solution would work. Indeed, if two nodes from the two linked lists are equal, it means they point to the same 'next node' object, which in turn will point to the same 'next node', etc. In this case, if the two linked list have a common node at some point, then the end of the two linked lists will be equal too. This, in turn, means that , if the two linked list have a common node, then this common node will be at the same position from the end in the two linked lists. Removing the extra nodes in the longest list and starting comparing from here thus work, in o(n).

For the case where elements of the list do not contain the reference to the 'next node' but only their value (such that you can have 1->2 in one list and 1->3 in the other), then we can think of a o(n) solution.
Suppose there is a way to traverse the list in the reverse order, beginning by the end and navigating to the previous (if the data structure does not enable it, then converting it into a data structurewhich enables it can be done in o(n) anyway). In this case, the algo would be :

0. mergingNode initialised to 'no merging node found (yet)'
1. currentNode from both lists = last node from both lists
2. compare both currentNodes
2.1 if they are different, return mergingNode
2.2 if they are equal :
2.2.1 mergingNode = currentNode
2.2.2 currentNodes from both list = previous element from both list (return mergingNode if one of the nodes does not exist - one list is finished)
2.2.3 go back to 2.
3. if we are here, the two lists are totally equal

This is an o(n) algorithm for that.

 

 

 

Reply