March LeetCoding Challenge 2021 — Day 4: Intersection of Two Linked Lists

We are going to solve the 4th problem from the March LeetCoding Challenge 2021.

Problem Statement

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.

Example 2:

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.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
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.

Notes:

• If the two linked lists have no intersection at all, return null.
• 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 [1, 10^9].
• Your code should preferably run in O(n) time and use only O(1) memory.

Solution

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)

Space Complexity:O(m)

Approach 2 — Constant Space: With this approach, we will traverse through both the Linked List, We take tempA pointing to headA and 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.

sksaikia/LeetCode

I have also posted previous problems from the March LeetCoding Challenge. Do check them out in my profile.