Intersection Point Of Linked Lists
1. You are given a partially written LinkedList class.Input Format
2. You are required to complete the body of findIntersection function. The 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.
3. Input and Output is managed for you.
Input is managed for youOutput Format
Output is managed for youQuestion Video
1. Time complexity > O(n)Sample Input
2. Space complexity > constant
5Sample Output
1 2 3 4 5
8
11 22 33 44 55 66 77 88
2
3
44

Editorial
The problem deals with finding the intersection point in a Y  shaped linked list. For example, given the linked list:
We have head1 as a > b > c > d > e > f having a length of 6 and head2 as g > d > e > f having a length of 4. Here we can see that the intersection point is a node with value d. To get this using code we will build our logic which goes like this:
1. head1.size > head2.size
This is the case when the distance of head1 from the intersection point is greater than that of head2, so to compensate we will traverse head1 to the point where the distance for both pointers becomes equal.
2. head1.size < head2.size
This is the case when the distance of head2 from the intersection point is greater than that of head1, so to compensate we will traverse head2 to the point where the distance for both pointers becomes equal.
When we have both pointers equidistance from the intersection point then we will traverse both lists at the same pace until we reach a common node and the first common node will be our intersection point.
So for the above list, firstly we would traverse list head1 until head1 points at node c. Now we will move both pointers to the next node and hence we reach a common node i.e. in this case node, hence node d is our resultant intersection point.
Below is the implementation in Java:
public static int findIntersection(LinkedList one, LinkedList two) { Node on = one.head; Node tn = two.head; if (one.size > two.size) { for (int i = 0; i < one.size  two.size; i++) { on = on.next; } } else { for (int i = 0; i < two.size  one.size; i++) { tn = tn.next; } } while (on != tn) { on = on.next; tn = tn.next; } return on.data; }
java false
Time Complexity: O(n+m)
The time complexity for the function is linear as for the worst case we would have to traverse both the lists entirely.
Space Complexity: O(1)
The space complexity for the function is constant as the approach is iterative without storing the list elements in any data structure except the input provided.

Asked in Companies

Related Topics