Intersection of Two linked List
Today we are going back to solving a Leet Code Problem. I took on myself to solve today’s Challenge problem
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
begin to intersect at node c1.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.So we have to find the intersection point between two linked list. This is easy right. Iterate through the first Linked List and for every node iterate through second linked list to find the intersection.
Not so fast, tiger. There is a catch you have to solve in O(n) time and O(1) space.
Whoa. This is going to be some piece of work. We can follow another approach. We can have a HashSet and store all the nodes of first list in it. and when iterating through the second list if its found in the set its the intersection we can return it.
So its solved in O(n) time but took O(n) space.
We’ve to optimize it now. How can we do this, One thing is certain though if they have been at equal length we can start from the beginning and go till the end to find if there is a same node.
This gave me a thought, how can we make it equal. So came an logic.
- Find the length of both linked lists
- Find the longer linked list and shorter linked list.
- Until the upcoming of length of longer linked list equals shorter linked list iterate through it.
- When they are at same length iterate through them both, if two nodes are equal this is an intersection.
- If no two equal nodes are found there is no intersection.
P.S : This is not my best version of code
#100DaysOfCode #Day14
