### Intersection of Two Linked Lists Java Program - The Coding Shala

Home >> Interview Questions >> Intersection of Two Linked Lists

## The intersection of Two Linked Lists

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,0,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,0,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 = [0,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 [0,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.

### The intersection of Two Linked List Java Program

Approach 1:
We can use two loops.
Time Complexity O(size1 * size2).

Java Code

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
while(tmp != null){
tmp = tmp.next;
}
}
return null;
}
}
```

Approach 2:
We can use the Hash Table. First, we store every node of the first linked list to the Hash table then check with the second linked list.

Time Complexity : O(size1 + size2).
Space Complexity: O(size1) or O(size2).

Java Code

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
HashSet<ListNode> map = new HashSet<ListNode>();
}
}
return null;
}
}
```

Approach 3:
We know that after the intersection point length of both the linked list is the same but before this length can be the same or not. Now if you find out the difference between the length and start from the same length then this can be solved in O(n) time.

We traverse both the linked list and when first linked list reach to null then point it to second linked list's head and same we do with the second linked list when it reaches to null assign it to the first's head. when both linked list's node match we return it.

Java Code

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {

while(first != second){
if(first == null) first = headB;
else first = first.next;
if(second == null) second = headA;
else second = second.next;
}
return first;
}
}
```

Approach 4:
First, we find out the length of both linked lists. We know after the intersection length is the same as both the lists.
Java Program:

```public class Solution {
int count1=0,count2=0;
while(tmpA!=null){
count1++;
tmpA=tmpA.next;
}
while(tmpB!=null){
count2++;
tmpB=tmpB.next;
}
int diff=Math.abs(count1-count2);
int len = 0;
if(count1>count2){
len = count1;
for(int i=0;i<diff;i++) tmpA=tmpA.next;
} else if(count2>count1){
len = count2;
for(int i=0;i<diff;i++) tmpB=tmpB.next;
}
while(tmpA != tmpB){
tmpA = tmpA.next;
tmpB = tmpB.next;
}
return tmpA;
}
}
```

Other Posts You May Like