# Intersection Point Of Linked Lists #### 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. `
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
`51 2 3 4 5811 22 33 44 55 66 77 8823`
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:

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.

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) {
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.

• Related Topics

Run

Run
Id Name