Redirecting to
NADOS

Intersection Point Of Linked Lists

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a partially written LinkedList class.
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. 

intersection-of-linked-list
Input Format 
Input is managed for you
Output Format 
Output is managed for you
Question Video
Constraints 
1. Time complexity -> O(n)
2. Space complexity -> constant
Sample Input 
5
1 2 3 4 5
8
11 22 33 44 55 66 77 88
2
3
Sample Output 
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






Video Solution

Code Solution

Run
 
Run
Id Name