In the given problem, a function is passed two linked lists which start separately but merge at a node and become common thereafter.
The function is expected to find the point where two linked lists merge. You are not allowed to use arrays to solve the problem.
- Time complexity -> O(n)
- Space complexity -> constant
Let the 2 input linked lists be 1-2-3-4-5-6 and 9-8-4-5-6 as shown in the figure 1.
Then, these two linked lists merge with each other at an intersection point "4".
The length of arms before the intersection point may not be the same for the linked lists. In our example, the length of the arm for the 1st linked list is 3 and for the 2nd linked list is 2.