Hey coder. Let's start the discussion of the last question under the topic of Linked Lists, "Intersection point of Linked Lists".
If you haven't already gone through the question, do it now.
Important Links : Question Video, Solution Video
INTERSECTION POINT OF LINKED LISTS
All endings are also beginnings. We just don't know it at the time.
~Mitch Albom
Hey coder. Let's start the discussion of the last question under the topic of Linked Lists, "Intersection point of Linked Lists".
If you haven't already gone through the question, do it now.
Important Links : Question Video, Solution Video
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.
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.
Reader, let's discuss the approach for this problem.
This approach works because after moving the pointer of the larger list by "delta" number of steps, the pointers t1 and t2 lie at equal distance from the point of intersection making it easy for us to find it.
Now that we have seen the algorithm for this problem, we try to code it .
java; true";
O(n)
Since a "while loop" is used in the program, therefore the time complexity is linear.
O(1)
Since no extra space is used in the program, therefore the space complexity is constant.
We highly suggest you watch the solution video for a better understanding of the discussion.
With this we conclude our question "Intersection Point of Linked Lists" as well as the topic of "Linked Lists". From the next lecture we will learn about "Generic Trees".
For now, Goodbye.