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.
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.
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
- If the two linked lists have no intersection at all, return
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Each value on each linked list is in the range
- Your code should preferably run in O(n) time and use only O(1) memory.
This problem can be solved in multiple ways. Here we will discuss two approaches.
Approach 1 — Using HashSet: Here, we are to find the intersection point between two Linked List. So the intersection point will be common in both the Linked List. Therefore we can use a HashSet to solve this problem. With this approach, we will store the nodes of the first Linked List in a HashSet. After that, we will traverse the second Linked List and check whether we have encountered that node before in the HashSet. When we find the first node which is present in the HashSet and the second list, we return it.
If m and n is the size of the first and second Linked List respectively, then
Time Complexity: O(m+n)
Approach 2 — Constant Space: With this approach, we will traverse through both the Linked List, We take
tempA pointing to
tempB pointing to
headB . As the Linked List is of different lengths, we have to take that into account. Whenever we reach the end of the first list, we set the
tempA to start of the second list and vice versa. In that way, once we have traversed both the lists, we will get the pointers traversing the same length. We run the loop until we find
tempA==tempB .A more detailed explanation can be found on the Leetcode solutions page.
Time Complexity : O(m+n)
Space Complexity: O(1)
The code can be found here also.
Contribute to sksaikia/LeetCode development by creating an account on GitHub.
I have also posted previous problems from the March LeetCoding Challenge. Do check them out in my profile.