Given two linked lists, where the tail of the second list points to a node in the first list, find the node where both lists intersect.
Consider the following linked lists where the second list’s tail is connected to the first list’s fourth node. The solution should return a pointer to the node 4 as the intersection point.
A simple solution is to consider each node of the first list and check if it can be reached from the second list. The first node in the first list that is reachable from the second list is the intersection point. The time complexity of this solution is O(N×M) where N is the length of the first list and M is the length of the second list.
However, the solution is far from optimal. This post provides an overview of several alternatives to improve the time complexity.
The idea is to traverse the first list and store each node’s address in a hash table. Then traverse the second list and get the address of the first node present in the hash table. This node would be the intersection point. Below is C++, Java, and Python implementation based on the above idea –
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
#include <iostream>
#include <unordered_set>
using namespace std;
// A linked list node
struct Node
{
int data;
Node* next;
};
// Utility function to create a new node with the given data and
// pushes it onto the front of the list
void push(Node*& headRef, int data)
{
// create a new linked list node from heap
Node* newNode = new Node;
newNode->data = data;
newNode->next = headRef;
headRef = newNode;
}
// Function to find the intersection point of two linked lists using hashing
Node* findIntersection(Node *first, Node *second)
{
// maintain a set to store list nodes
unordered_set<Node*> nodes;
// traverse the first list and insert the address of each node in the set
while (first)
{
nodes.insert(first);
first = first->next;
}
// Now traverse the second list and find the first node that is
// already present in the set
while (second)
{
// return current node if found in the set
if (nodes.find(second) != nodes.end()) {
return second;
}
second = second->next;
}
// we reach here if lists do not intersect
return nullptr;
}
int main()
{
// construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> null)
Node* first = nullptr;
for (int i = 5; i > 0; i—)
push(first, i);
// construct the second linked list (1 -> 2 -> 3 -> null)
Node* second = nullptr;
for (int i = 3; i > 0; i—)
push(second, i);
// link tail of the second list to fourth node of the first list
second->next->next->next = first->next->next->next;
Node* addr = findIntersection(first, second);
if (addr) {
cout << “The intersection point is “ << addr->data << endl;
}
else {
cout << “The lists do not intersect.” << endl;
}
return 0;
}
|
Output:
The intersection point is 4
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
import java.util.HashSet;
import java.util.Set;
// A linked list node
class Node {
int data;
Node next;
}
class Main {
// Utility function to create a new node with the given data and
// pushes it onto the front of the list
public static Node push(Node head, int data) {
Node node = new Node();
node.data = data;
node.next = head;
return node;
}
// Function to find the intersection point of two linked lists using hashing
public static Node findIntersection(Node first, Node second)
{
// maintain a HashSet to store list nodes
Set<Node> nodes = new HashSet<>();
// traverse the first list and insert the address of each node in the HashSet
while (first != null)
{
nodes.add(first);
first = first.next;
}
// Now traverse the second list and find the first node that is
// already present in the HashSet
while (second != null)
{
// return current node if found in the HashSet
if (nodes.contains(second)) {
return second;
}
second = second.next;
}
// we reach here if lists do not intersect
return null;
}
public static void main(String[] args)
{
// construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> null)
Node first = null;
for (int i = 5; i > 0; i—) {
first = push(first, i);
}
// construct the second linked list (1 -> 2 -> 3 -> null)
Node second = null;
for (int i = 3; i > 0; i—) {
second = push(second, i);
}
// link tail of the second list to fourth node of the first list
second.next.next.next = first.next.next.next;
Node addr = findIntersection(first, second);
if (addr != null) {
System.out.println(“The intersection point is “ + addr.data);
}
else {
System.out.println(“The lists do not intersect.”);
}
}
}
|
Output:
The intersection point is 4
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
# A linked list node
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
# Function to find the intersection point of two linked lists using hashing
def findIntersection(first, second):
# maintain a set to store list nodes
nodes = set()
# traverse the first list and insert the address of each node in the set
while first:
nodes.add(first)
first = first.next
# Now traverse the second list and find the first node that is
# already present in the set
while second:
# return current node if found in the set
if second in nodes:
return second
second = second.next
# we reach here if lists do not intersect
return None
if __name__ == ‘__main__’:
# construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> None)
first = None
for i in reversed(range(1, 6)):
first = Node(i, first)
# construct the second linked list (1 -> 2 -> 3 -> None)
second = None
for i in reversed(range(1, 4)):
second = Node(i, second)
# link tail of the second list to fourth node of the first list
second.next.next.next = first.next.next.next
addr = findIntersection(first, second)
if addr:
print(“The intersection point is”, addr.data)
else:
print(“The lists do not intersect.”)
|
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
The time complexity of the above solution is O(N + M) where N is the length of the first list and M is the length of the second list. However, the program uses O(N) additional space for storing nodes of the first list in a hash table.
Another approach is to make the first linked list circular by linking its tail to the head. Then, the problem reduces to finding a loop in the second linked list.
The idea is to get a pointer to the loop node using Floyd’s Cycle detection algorithm and count the number of nodes in the loop using that loop node (say k). Then take two pointers – one pointing to the head node and another pointing to the k'th node from the head. If we simultaneously move these pointers at the same speed, they will eventually meet at the loop’s starting node.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
#include <iostream>
#include <unordered_set>
using namespace std;
// A linked list node
struct Node
{
int data;
Node* next;
};
// Utility function to create a new node with the given data and
// pushes it onto the front of the list
void push(Node*& headRef, int data)
{
// create a new linked list node from heap
Node* newNode = new Node;
newNode->data = data;
newNode->next = headRef;
headRef = newNode;
}
// Find the starting node of the loop in the linked list pointed by `head`
// The `loopNode` points to one of the nodes involved in the cycle
Node* removeCycle(Node* loopNode, Node* head)
{
// Find the count of nodes involved in the loop and store the count in ‘k’
int k = 1;
for (Node* ptr = loopNode; ptr->next != loopNode; ptr = ptr->next) {
k++;
}
// Get pointer to k’th node from the head
Node *curr = head;
for (int i = 0; i < k; i++) {
curr = curr->next;
}
// Simultaneously move the `head` and `curr` pointers
// at the same speed until they meet
while (curr != head)
{
curr = curr->next;
head = head->next;
}
// `curr` now points to the starting node of the loop
return curr;
}
// Function to identify cycle in a linked list using
// Floyd’s Cycle Detection Algorithm
Node* identifyCycle(Node *head)
{
// take two pointers – slow and fast
Node *slow = head, *fast = head;
while (fast && fast->next)
{
// move slow by one pointer
slow = slow->next;
// move fast by two pointers
fast = fast->next->next;
// if they meet any node, linked list contains a cycle
if (slow == fast) {
return slow;
}
}
// return null if linked list does not contain a cycle
return nullptr;
}
// Function to find the intersection point of two linked lists
Node* findIntersection(Node *first, Node *second)
{
Node *prev = nullptr; // previous pointer
Node *curr = first; // main pointer
// traverse the first list
while (curr)
{
// update previous pointer to the current node and
// move main pointer to the next node
prev = curr;
curr = curr->next;
}
// create cycle in the first list
if (prev) {
prev->next = first;
}
// Now get pointer to the loop node using the second list
Node* slow = identifyCycle(second);
// find the intersection node
Node* addr = nullptr;
if (slow) {
addr = removeCycle(slow, second);
}
// remove cycle in the first list before exiting
if (prev) {
prev->next = nullptr;
}
// return the intersection node
return addr;
}
int main()
{
// construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> null)
Node* first = nullptr;
for (int i = 7; i > 0; i—)
push(first, i);
// construct the second linked list (1 -> 2 -> 3 -> null)
Node* second = nullptr;
for (int i = 3; i > 0; i—)
push(second, i);
// link tail of the second list to fourth node of the first list
second->next->next->next = first->next->next->next;
Node* addr = findIntersection(first, second);
if (addr) {
cout << “The intersection point is “ << addr->data << endl;
}
else {
cout << “The lists do not intersect.” << endl;
}
return 0;
}
|
Output:
The intersection point is 4
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
// A linked list node
class Node {
int data;
Node next;
}
class Main
{
// Utility function to create a new node with the given data and
// pushes it onto the front of the list
public static Node push(Node head, int data)
{
Node node = new Node();
node.data = data;
node.next = head;
return node;
}
// Find the starting node of the loop in the linked list pointed by `head`.
// The `loopNode` points to one of the nodes involved in the cycle
public static Node removeCycle(Node loopNode, Node head)
{
// Find the count of nodes involved in the loop and store the count in ‘k’
int k = 1;
for (Node ptr = loopNode; ptr.next != loopNode; ptr = ptr.next) {
k++;
}
// Get pointer to k’th node from the head
Node curr = head;
for (int i = 0; i < k; i++) {
curr = curr.next;
}
// Simultaneously move the `head` and `curr` pointers
// at the same speed until they meet
while (curr != head) {
curr = curr.next;
head = head.next;
}
// `curr` now points to the starting node of the loop
return curr;
}
// Function to identify cycle in a linked list using
// Floyd’s Cycle Detection Algorithm
public static Node identifyCycle(Node head)
{
// take two pointers – slow and fast
Node slow = head, fast = head;
while (fast != null && fast.next != null)
{
// move slow by one pointer
slow = slow.next;
// move fast by two pointers
fast = fast.next.next;
// if they meet any node, linked list contains a cycle
if (slow == fast) {
return slow;
}
}
// return null if linked list does not contain a cycle
return null;
}
// Function to find the intersection point of two linked lists
public static Node findIntersection(Node first, Node second)
{
Node prev = null; // previous pointer
Node curr = first; // main pointer
// traverse the first list
while (curr != null)
{
// update previous pointer to the current node and
// move main pointer to the next node
prev = curr;
curr = curr.next;
}
// create cycle in the first list
if (prev != null) {
prev.next = first;
}
// Now get pointer to the loop node using the second list
Node slow = identifyCycle(second);
// find the intersection node
Node addr = null;
if (slow != null) {
addr = removeCycle(slow, second);
}
// remove cycle in the first list before exiting
if (prev != null) {
prev.next = null;
}
// return the intersection node
return addr;
}
public static void main(String[] args)
{
// construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> null)
Node first = null;
for (int i = 7; i > 0; i—) {
first = push(first, i);
}
// construct the second linked list (1 -> 2 -> 3 -> null)
Node second = null;
for (int i = 3; i > 0; i—) {
second = push(second, i);
}
// link tail of the second list to fourth node of the first list
second.next.next.next = first.next.next.next;
Node addr = findIntersection(first, second);
if (addr != null) {
System.out.println(“The intersection point is “ + addr.data);
}
else {
System.out.println(“The lists do not intersect”);
}
}
}
|
Output:
The intersection point is 4
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
# A linked list node
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
# Find the starting node of the loop in linked list pointed by `head`
# The `loop_node` points to one of the nodes involved in the cycle
def removeCycle(loop_node, head):
# Find the count of nodes involved in the loop and store the count in ‘k’
k = 1
ptr = loop_node
while ptr.next is not loop_node:
k += 1
ptr = ptr.next
# Get pointer to k’th node from the head
curr = head
for _ in range(k):
curr = curr.next
# Simultaneously move the `head` and `curr` pointers
# at the same speed until they meet
while curr is not head:
curr = curr.next
head = head.next
# `curr` now points to the starting node of the loop
return curr
# Function to identify cycle in a linked list using
# Floyd’s Cycle Detection Algorithm
def identifyCycle(head):
# take two pointers – slow and fast
slow = fast = head
while fast and fast.next:
# move slow by one pointer
slow = slow.next
# move fast by two pointers
fast = fast.next.next
# if they meet any node, linked list contains a cycle
if slow == fast:
return slow
# return None if the linked list does not contain a cycle
return None
# Function to find the intersection point of two linked lists
def findIntersection(first, second):
prev = None # previous pointer
curr = first # main pointer
# traverse the first list
while curr:
# update previous pointer to the current node and
# move main pointer to the next node
prev = curr
curr = curr.next
# create cycle in the first list
if prev:
prev.next = first
# Now get pointer to the loop node using the second list
slow = identifyCycle(second)
# find the intersection node
addr = None
if slow:
addr = removeCycle(slow, second)
# remove cycle in the first list before exiting
if prev:
prev.next = None
# return the intersection node
return addr
if __name__ == ‘__main__’:
# construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> None)
first = None
for i in reversed(range(1, 6)):
first = Node(i, first)
# construct the second linked list (1 -> 2 -> 3 -> None)
second = None
for i in reversed(range(1, 4)):
second = Node(i, second)
# link tail of the second list to fourth node of the first list
second.next.next.next = first.next.next.next
addr = findIntersection(first, second)
if addr:
print(“The intersection point is”, addr.data)
else:
print(“The lists do not intersect.”)
|
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
The time complexity of the above solution is O(N + M) where N is the length of the first list and M is the length of the second list.
We can also use the difference in node counts of both lists to find the intersection point. The idea is to advance the bigger list by k nodes, where k is the difference in the number of nodes in both lists. Then, move both lists at the same speed until they intersect with each other. The node at which both lists intersect is the intersection point.
This logic can be implemented as follows in C++, Java, and Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#include <iostream>
using namespace std;
// A linked list node
struct Node
{
int data;
Node* next;
};
// Utility function to create a new node with the given data and
// pushes it onto the front of the list
void push(Node*& headRef, int data)
{
// create a new linked list node from heap
Node* newNode = new Node;
newNode->data = data;
newNode->next = headRef;
headRef = newNode;
}
// Utility function to find the number of nodes in the linked list
int size(Node* head)
{
int nodes = 0;
for (Node *curr = head; curr != nullptr; curr = curr->next) {
nodes++;
}
return nodes;
}
// Function to find the intersection point of two linked lists
// Assume that the first list contains `k` nodes more than the second list
Node* findIntersection(Node* first, Node* second, int k)
{
// Advance the bigger list by `k` nodes
for (int i = 0; i < k && first; i++) {
first = first->next;
}
// Simultaneously move both lists at the same speed until they meet
while (first && second)
{
// if both lists meet any node, then that node is the intersection point
if (first == second) {
return first;
}
// Advance both lists by one node
first = first->next;
second = second->next;
}
// return null if both lists doesn’t meet
return nullptr;
}
// Function to find the intersection point of two linked lists
Node* findIntersection(Node *first, Node *second)
{
// get the difference in number of nodes in both lists
int diff = size(first) – size(second);
// if the first list has a smaller number of nodes, exchange both lists
if (diff < 0) {
swap(first, second);
}
// find and return the intersection node
return findIntersection(first, second, abs(diff));
}
int main()
{
// construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> null)
Node* first = nullptr;
for (int i = 7; i > 0; i—)
push(first, i);
// construct the second linked list (1 -> 2 -> 3 -> null)
Node* second = nullptr;
for (int i = 3; i > 0; i—)
push(second, i);
// link tail of the second list to fourth node of the first list
second->next->next->next = first->next->next->next;
Node* addr = findIntersection(first, second);
if (addr) {
cout << “The intersection point is “ << addr->data << endl;
}
else {
cout << “The lists do not intersect.” << endl;
}
return 0;
}
|
Output:
The intersection point is 4
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
// A linked list node
class Node {
int data;
Node next;
}
class Main
{
// Utility function to create a new node with the given data and
// pushes it onto the front of the list
public static Node push(Node head, int data) {
Node node = new Node();
node.data = data;
node.next = head;
return node;
}
// Utility function to find the number of nodes in the linked list
public static int size(Node head)
{
int nodes = 0;
for (Node curr = head; curr != null; curr = curr.next) {
nodes++;
}
return nodes;
}
// Function to find the intersection point of two linked lists
// Assume that the first list contains `k` nodes more than the second list
public static Node findIntersection(Node first, Node second, int k)
{
// Advance the bigger list by `k` nodes
for (int i = 0; i < k && first!= null; i++) {
first = first.next;
}
// Simultaneously move both lists at the same speed until they meet
while (first != null && second != null)
{
// if both lists meet any node, then that node is the intersection point
if (first == second) {
return first;
}
// Advance both lists by one node
first = first.next;
second = second.next;
}
// return null if both lists doesn’t meet
return null;
}
// Function to find the intersection point of two linked lists
public static Node findIntersection(Node first, Node second)
{
// get the difference in number of nodes in both lists
int diff = size(first) – size(second);
// if the first list has a smaller number of nodes, exchange both lists
if (diff < 0) {
Node node = first;
first = second;
second = node;
}
// find and return the intersection node
return findIntersection(first, second, Math.abs(diff));
}
public static void main(String[] args)
{
// construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> null)
Node first = null;
for (int i = 7; i > 0; i—) {
first = push(first, i);
}
// construct the second linked list (1 -> 2 -> 3 -> null)
Node second = null;
for (int i = 3; i > 0; i—) {
second = push(second, i);
}
// link tail of the second list to fourth node of the first list
second.next.next.next = first.next.next.next;
Node addr = findIntersection(first, second);
if (addr != null) {
System.out.println(“The intersection point is “ + addr.data);
}
else {
System.out.println(“The lists do not intersect.”);
}
}
}
|
Output:
The intersection point is 4
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
# A linked list node
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
# Utility function to find the number of nodes in the linked list
def size(head):
nodes = 0
while head:
nodes += 1
head = head.next
return nodes
# Function to find the intersection point of two linked lists
# Assume that the first list contains `k` nodes more than the second list
def findIntersection(first, second, k):
# Advance the bigger list by `k` nodes
i = 0
while i < k and first:
first = first.next
i += 1
# Simultaneously move both lists at the same speed until they meet
while first and second:
# if both lists meet any node, then that node is the intersection point
if first == second:
return first
# Advance both lists by one node
first = first.next
second = second.next
# return None if both lists don’t meet
return None
# Function to find the intersection point of two linked lists
def findIntersectionPt(first, second):
# get the difference in number of nodes in both lists
diff = size(first) – size(second)
# if the first list has a smaller number of nodes, exchange both lists
if diff < 0:
node = first
first = second
second = node
# find and return the intersection node
return findIntersection(first, second, abs(diff))
if __name__ == ‘__main__’:
# construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> None)
first = None
for i in reversed(range(1, 6)):
first = Node(i, first)
# construct the second linked list (1 -> 2 -> 3 -> None)
second = None
for i in reversed(range(1, 4)):
second = Node(i, second)
# link tail of the second list to fourth node of the first list
second.next.next.next = first.next.next.next
addr = findIntersectionPt(first, second)
if addr:
print(“The intersection point is”, addr.data)
else:
print(“The lists do not intersect.”)
|
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
The time complexity of the above solution is O(N + M) where N is the length of the first list and M is the length of the second list.
Observation: The number of nodes in the first list + distance of the head of the second list from the intersection point = The number of nodes in the second list + distance of the head of the first list from the intersection point.
The idea is to take two pointers, x and y, initially pointing to the head of the first list and the second list’s head, respectively. Then, advance both pointers at the same pace until they meet at a common node. When x reaches its end, redirect it to the head of the second list. When y reaches its end, turn it to the head of the first list. The node where x meets y is the intersection node.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <iostream>
using namespace std;
// A linked list node
struct Node
{
int data;
Node* next;
};
// Utility function to create a new node with the given data and
// pushes it onto the front of the list
void push(Node*& headRef, int data)
{
// create a new linked list node from heap
Node* newNode = new Node;
newNode->data = data;
newNode->next = headRef;
headRef = newNode;
}
// Function to find the intersection point of two linked lists
Node* findIntersection(Node *first, Node *second)
{
// Take two pointers pointing to the heads of respective lists
Node *x = first, *y = second;
// Advance both pointers until they meet at common node
while (x != y)
{
// When the first list reaches its end, redirect it to the
// head of the second list
if (x == nullptr) {
x = second;
}
else {
x = x->next;
}
// When the second list reaches its end, redirect it to the
// head of the first list
if (y == nullptr) {
y = first;
}
else {
y = y->next;
}
}
// return the common node
return x;
}
int main()
{
// construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> null)
Node* first = nullptr;
for (int i = 7; i > 0; i—)
push(first, i);
// construct the second linked list (1 -> 2 -> 3 -> null)
Node* second = nullptr;
for (int i = 3; i > 0; i—)
push(second, i);
// link tail of the second list to fourth node of the first list
second->next->next->next = first->next->next->next;
Node* addr = findIntersection(first, second);
if (addr) {
cout << “The intersection point is “ << addr->data << endl;
}
else {
cout << “The lists do not intersect.” << endl;
}
return 0;
}
|
Output:
The intersection point is 4
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
// A linked list node
class Node
{
int data;
Node next;
}
class Main
{
// Utility function to create a new node with the given data and
// pushes it onto the front of the list
public static Node push(Node head, int data)
{
// create a new linked list node from heap
Node node = new Node();
node.data = data;
node.next = head;
return node;
}
// Function to find the intersection point of two linked lists
public static Node findIntersection(Node first, Node second)
{
// Take two pointers pointing to the heads of respective lists
Node x = first, y = second;
// Advance both pointers until they meet at common node
while (x != y)
{
// When the first list reaches its end, redirect it to the
// head of the second list
if (x == null) {
x = second;
}
else {
x = x.next;
}
// When the second list reaches its end, redirect it to the
// head of the first list
if (y == null) {
y = first;
}
else {
y = y.next;
}
}
// return the common node
return x;
}
public static void main(String[] args)
{
// construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> null)
Node first = null;
for (int i = 7; i > 0; i—) {
first = push(first, i);
}
// construct the second linked list (1 -> 2 -> 3 -> null)
Node second = null;
for (int i = 3; i > 0; i—) {
second = push(second, i);
}
// link tail of the second list to fourth node of the first list
second.next.next.next = first.next.next.next;
Node addr = findIntersection(first, second);
if (addr != null) {
System.out.println(“The intersection point is “ + addr.data);
}
else {
System.out.println(“The lists do not intersect.”);
}
}
}
|
Output:
The intersection point is 4
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
# A linked list node
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
# Function to find the intersection point of two linked lists
def findIntersection(first, second):
# Take two pointers pointing to the heads of respective lists
x = first
y = second
# Advance both pointers until they meet at common node
while x != y:
# When the first list reaches its end, redirect it to the
# head of the second list
if x is None:
x = second
else:
x = x.next
# When the second list reaches its end, redirect it to the
# head of the first list
if y is None:
y = first
else:
y = y.next
# return the common node
return x
if __name__ == ‘__main__’:
# construct the first linked list (1 -> 2 -> 3 -> 4 -> 5 -> None)
first = None
for i in reversed(range(1, 6)):
first = Node(i, first)
# construct the second linked list (1 -> 2 -> 3 -> None)
second = None
for i in reversed(range(1, 4)):
second = Node(i, second)
# link tail of the second list to fourth node of the first list
second.next.next.next = first.next.next.next
addr = findIntersection(first, second)
if addr:
print(“The intersection point is”, addr.data)
else:
print(“The lists do not intersect.”)
|
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
Download Run Code
Output:
The intersection point is 4
The time complexity of the above solution is O(N + M) where N is the length of the first list and M is the length of the second list.