How do i find the common node point of 2 single linked lists?

user_11909972 0
Viewed 186

My approach to this question was to use a hashmap for storing the addresses of first linked list and traversing the second array and checking whether i found the address or not .If it is found i would return the node at that address. This would take O(m+n),where m and n are lengths of linked list but here we are using O(Linear) space complexity. I found another approach to this question which has constant space but same time complexity but it didn't clear my doubt. link to the question

what if my input is

    list 11 = 1 -> 2 -> 3 -> 4 -> 6 ->7;
    list l2 = 2 -> 9;

In this case my one time traversal of lists after truncating the extra length would become like this

   diff=4;   // i would advance the list 1 by 4 elements as it has greater length
   l1= 6-> 7;
   l2= 2 -> 9;

Here i lost my intersection node . Can someone help me with this?

c algorithm c++ java
1 Answers

That method is only valid when the input linked lists are the same from the intersection point like :

1 -> 2 -> 3 -> 4 -> 5

12 -> 11-> 10 -> 3 -> 4 -> 5

Here the two lists are the same from the intersection point 3.

Only then that algorithm works.

Note :

This problem is basically given as to find the intersection point of an inverted Y-shaped list (combination of two lists)

user_107586540
Related