# Find intersection of Two Linked Lists

Problem Statement: Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

Examples:

```Example 1:
Input:
List 1 = [1,3,1,2,4], List 2 = [3,2,4]
Output:
2
Explanation: Here, both lists intersecting nodes start from node 2.
```
```Example 2:
Input:
List1 = [1,2,7], List 2 = [2,8,1]
Output:
Null
Explanation: Here, both lists do not intersect and thus no intersection node is present.
```

Solution 1: Brute-Force

Approach: We know intersection means a common attribute present between two entities. Here, we have linked lists as given entities.

What should be the common attribute for two linked lists?

If you believe a common attribute is a node’s value, then think properly! If we take our example 1, there we can see both lists have nodes of value 3. But it is not the first intersection node. So what’s the common attribute?

It is the node itself that is the common attribute. So, the process is as follows:-

• Keep any one of the list to check its node present in the other list. Here, we are choosing the second list for this task.
• Iterate through the other list. Here, it is the first one.
• Check if the both nodes are the same. If yes, we got our first intersection node.
• If not, continue iteration.
• If we did not find an intersection node and completed the entire iteration of the second list, then there is no intersection between the provided lists. Hence, return null.

Dry Run:

Code:

## C++ Code

``````#include<iostream>
using namespace std;

class node {
public:
int num;
node* next;
node(int val) {
num = val;
next = NULL;
}
};
//utility function to insert node at the end of the linked list
node* newNode = new node(val);

return;
}

while(temp->next != NULL) temp = temp->next;

temp->next = newNode;
return;
}

//utility function to check presence of intersection
while(temp != NULL) {
//if both nodes are same
temp = temp->next;
}
}
//intersection is not present between the lists return null
return NULL;
}

//utility function to print linked list created
}
}

int main() {
// creation of both lists
//printing of the lists
//checking if intersection is present
cout<<"No intersection\n";
else
return 0;
}
``````

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity: O(m*n)

Reason: For each node in list 2 entire lists 1 are iterated.

Space Complexity: O(1)

Reason: No extra space is used.

## Java Code

``````import java.util.*;
class Node {
int num;
Node next;
Node(int val) {
num = val;
next = null;
}
}
class TUF{
//utility function to insert node at the end of the linked list
static Node insertNode(Node head,int val) {
Node newNode = new Node(val);

}

while(temp.next != null) temp = temp.next;

temp.next = newNode;
}

//utility function to check presence of intersection
while(temp != null) {
//if both nodes are same
temp = temp.next;
}
}
//intersection is not present between the lists return null
return null;
}

//utility function to print linked list created
}
}

public static void main(String args[]) {
// creation of both lists
//printing of the lists
//checking if intersection is present
System.out.println("No intersection\n");
else

}
}``````

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity: O(m*n)

Reason: For each node in list 2 entire lists 1 are iterated.

Space Complexity: O(1)

Reason: No extra space is used.

## Python Code

``````class Node:
def __init__(self, val):
self.val = val
self.next = None

# utility function to insert node at the end of the linked list
newNode = Node(val)
while temp.next != None:
temp = temp.next
temp.next = newNode

# utility function to check presence of intersection
while temp != None:
# if both nodes are same
temp = temp.next
# intersection is not present between the lists
return None

# utility function to print linked list created

if __name__ == '__main__':
print('List1: ', end='')
print('List2: ', end='')
print('No intersection')
else:

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity: O(m*n)

Reason: For each node in list 2 entire list 1 is iterated.

Space Complexity: O(1)

Reason: No extra space is used.

Solution 2: Hashing

Approach:

Can we improve brute-force time complexity? In brute force, we are basically performing “searching”. We can also perform searches by Hashing. Taking into consideration that hashing process takes O(1) time complexity. So the process is as follows:-

• Iterate through list 1 and hash its node address. Why? (Hint: depends on the common attribute we are searching)
• Iterate through list 2 and search the hashed value in the hash table. If found, return node.

Code:

## C++ Code

``````#include<bits/stdc++.h>
using namespace std;

class node {
public:
int num;
node* next;
node(int val) {
num = val;
next = NULL;
}
};
//utility function to insert node at the end of the linked list
node* newNode = new node(val);

return;
}

while(temp->next != NULL) temp = temp->next;

temp->next = newNode;
return;
}

//utility function to check presence of intersection
unordered_set<node*> st;
}
}
return NULL;

}

//utility function to print linked list created
}
}

int main() {
// creation of both lists
//printing of the lists
//checking if intersection is present
cout<<"No intersection\n";
else
return 0;
}
``````

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity: O(n+m)

Reason: Iterating through list 1 first takes O(n), then iterating through list 2 takes O(m).

Space Complexity: O(n)

Reason: Storing list 1 node addresses in unordered_set.

## Java Code

``````import java.util.*;
class Node {
int num;
Node next;
Node(int val) {
num = val;
next = null;
}
}
class TUF{
//utility function to insert node at the end of the linked list
static Node insertNode(Node head,int val) {
Node newNode = new Node(val);

}

while(temp.next != null) temp = temp.next;

temp.next = newNode;
}

//utility function to check presence of intersection
HashSet<Node> st=new HashSet<>();
}
}
return null;

}

//utility function to print linked list created
}
}

public static void main(String args[]) {
// creation of both lists
//printing of the lists
//checking if intersection is present
System.out.println("No intersection\n");
else

}
}``````

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity: O(n+m)

Reason: Iterating through list 1 first takes O(n), then iterating through list 2 takes O(m).

Space Complexity: O(n)

Reason: Storing list 1 node address in HashSet.

## Python Code

``````class Node:
def __init__(self, val):
self.val = val
self.next = None

# utility function to insert node at the end of the linked list
newNode = Node(val)
while temp.next != None:
temp = temp.next
temp.next = newNode

# utility function to check presence of intersection
st = set()
return None

# utility function to print linked list created

if __name__ == '__main__':
print('List1: ', end='')
print('List2: ', end='')
print('No intersection')
else:

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity: O(n+m)

Reason: Iterating through list 1 first takes O(n), then iterating through list 2 takes O(m).

Space Complexity: O(n)

Reason: Storing list 1 node addresses in unordered_set.

Solution 3: Difference in length

Approach:

We will reduce the search length. This can be done by searching the length of the shorter linked list. How? Let’s see the process.

• Find the length of both lists.
• Find the positive difference between these lengths.
• Move the dummy pointer of the larger list by the difference achieved. This makes our search length reduced to a smaller list length.
• Move both pointers, each pointing two lists, ahead simultaneously if both do not collide.

Dry Run:

Code:

## C++ Code

``````#include<bits/stdc++.h>
using namespace std;

class node {
public:
int num;
node* next;
node(int val) {
num = val;
next = NULL;
}
};
//utility function to insert node at the end of the linked list
node* newNode = new node(val);

return;
}

while(temp->next != NULL) temp = temp->next;

temp->next = newNode;
return;
}
int len1 = 0,len2 = 0;
}
}

}
return len1-len2;//if difference is neg-> length of list2 > length of list1 else vice-versa
}

//utility function to check presence of intersection
if(diff < 0)
}

}

//utility function to print linked list created
}
}

int main() {
// creation of both lists
//printing of the lists
//checking if intersection is present
cout<<"No intersection\n";
else
return 0;
}
``````

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity:

O(2max(length of list1,length of list2))+O(abs(length of list1-length of list2))+O(min(length of list1,length of list2))

Reason: Finding the length of both lists takes max(length of list1, length of list2) because it is found simultaneously for both of them. Moving the head pointer ahead by a difference of them. The next one is for searching.

Space Complexity: O(1)

Reason: No extra space is used.

## Java Code

``````import java.util.*;
class Node {
int num;
Node next;
Node(int val) {
num = val;
next = null;
}
}
class TUF{
//utility function to insert node at the end of the linked list
static Node insertNode(Node head,int val) {
Node newNode = new Node(val);

}

while(temp.next != null) temp = temp.next;

temp.next = newNode;
}
int len1 = 0,len2 = 0;
}
}

}
return len1-len2;//if difference is neg-> length of list2 > length of list1 else vice-versa
}
//utility function to check presence of intersection
if(diff < 0)
}

}

//utility function to print linked list created
}
}

public static void main(String args[]) {
// creation of both lists
//printing of the lists
//checking if intersection is present
System.out.println("No intersection\n");
else

}
}``````

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity:

O(2max(length of list1,length of list2))+O(abs(length of list1-length of list2))+O(min(length of list1,length of list2))

Reason: Finding the length of both lists takes max(length of list1, length of list2) because it is found simultaneously for both of them. Moving the head pointer ahead by a difference of them. The next one is for searching.

Space Complexity: O(1)

Reason: No extra space is used.

## Python Code

``````class Node:
def __init__(self, val):
self.val = val
self.next = None

# utility function to insert node at the end of the linked list
newNode = Node(val)
while temp.next != None:
temp = temp.next
temp.next = newNode

len1 = 0
len2 = 0
len1 += 1
len2 += 1
# if difference is neg-> length of list2 > length of list1 else vice-versa
return len1 - len2

# utility function to check presence of intersection
if diff < 0:
while diff != 0:
diff += 1
else:
while diff != 0:
diff -= 1

# utility function to print linked list created

if __name__ == '__main__':
print('List1: ', end='')
print('List2: ', end='')
print('No intersection')
else:

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity:

O(2max(length of list1,length of list2))+O(abs(length of list1-length of list2))+O(min(length of list1,length of list2))

Reason: Finding the length of both lists takes max(length of list1, length of list2) because it is found simultaneously for both of them. Moving the head pointer ahead by a difference of them. The next one is for searching.

Space Complexity: O(1)

Reason: No extra space is used.

Solution 4: Optimised

Approach:

The difference of length method requires various steps to work on it. Using the same concept of difference of length, a different approach can be implemented. The process is as follows:-

• Take two dummy nodes for each list. Point each to the head of the lists.
• Iterate over them. If anyone becomes null, point them to the head of the opposite lists and continue iterating until they collide.

Dry Run:

Code:

## C++ Code

``````#include<bits/stdc++.h>
using namespace std;

class node {
public:
int num;
node* next;
node(int val) {
num = val;
next = NULL;
}
};
//utility function to insert node at the end of the linked list
node* newNode = new node(val);

return;
}

while(temp->next != NULL) temp = temp->next;

temp->next = newNode;
return;
}
//utility function to check presence of intersection

while(d1 != d2) {
d1 = d1 == NULL? head2:d1->next;
d2 = d2 == NULL? head1:d2->next;
}

return d1;
}

//utility function to print linked list created
}
}

int main() {
// creation of both lists
//printing of the lists
//checking if intersection is present
cout<<"No intersection\n";
else
return 0;
}
``````

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity: O(2*max(length of list1,length of list2))

Reason: Uses the same concept of the difference of lengths of two lists.

Space Complexity: O(1)

Reason: No extra data structure is used

## Java Code

``````import java.util.*;
class Node {
int num;
Node next;
Node(int val) {
num = val;
next = null;
}
}
class TUF{
//utility function to insert node at the end of the linked list
static Node insertNode(Node head,int val) {
Node newNode = new Node(val);

}

while(temp.next != null) temp = temp.next;

temp.next = newNode;
}
//utility function to check presence of intersection

while(d1 != d2) {
d1 = d1 == null? head2:d1.next;
d2 = d2 == null? head1:d2.next;
}

return d1;
}

//utility function to print linked list created
}
}

public static void main(String args[]) {
// creation of both lists
//printing of the lists
//checking if intersection is present
System.out.println("No intersection\n");
else

}
}``````

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity: O(2*max(length of list1,length of list2))

Reason: Uses the same concept of the difference of lengths of two lists.

Space Complexity: O(1)

Reason: No extra data structure is used

## Python Code

``````class Node:
def __init__(self, val):
self.val = val
self.next = None

# utility function to insert node at the end of the linked list
newNode = Node(val)
while temp.next != None:
temp = temp.next
temp.next = newNode

# utility function to check presence of intersection
while d1 != d2:
d1 = head2 if d1 == None else d1.next
d2 = head1 if d2 == None else d2.next
return d1

# utility function to print linked list created

if __name__ == '__main__':
print('List1: ', end='')
print('List2: ', end='')
print('No intersection')
else:

Output:

List1: 1->3->1->2->4
List2: 3->2->4
The intersection point is 2

Time Complexity: O(2*max(length of list1,length of list2))

Reason: Uses the same concept of difference of lengths of two lists.

Space Complexity: O(1)

Reason: No extra data structure is used