Find the location where two linked lists intersect.
Find the node where the two linked lists cross when there are two of them and the tail of the second list points to a node in the first list.
Take into account the linked lists below, where the fourth node of the first list is connected to the tail of the second list. The intersection point, node 4, should be the solution’s return value.
1) Consider each node in the first list and determine whether it can be accessed from the second list as a straightforward solution. The intersection point is the first node in the first list that can be reached from the second list. The total number of nodes in the first and second lists, m and n, respectively, determine the solution’s time complexity, which is O(m.n).
- Day 30:Kubernetes- Recap and Next Steps
- Day 29: Kubernetes – Exploring the Kubernetes Ecosystem
- Day 28: Kubernetes – Cost Optimization in Kubernetes
- Day 27: Kubernetes – Kubernetes for Machine Learning Workloads
- Day 26: Kubernetes – GitOps with Kubernetes
1.Utilizing Hashing
The plan is to go through the first list and put the addresses of each node in a hash table. the address of the first node that is present in the hash table by traversing the second list. The intersection would happen at this node. The idea’s implementation in C++, Java, and Python is as follows:
The solution is not ideal, though. This article offers a summary of a number of runtime improvement options.
C++ :
#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 list's front
void push(Node*& headRef, int data)
{
// create a new linked list node from the 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 into 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 the current node if it is 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 the 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;
}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 list's front
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 set to store list nodes
Set<Node> nodes = new HashSet<>();
// traverse the first list and insert the address of each node into the set
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 set
while (second != null)
{
// return the current node if it is found in the set
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 the 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.");
}
}
}# 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 into 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 the current node if it is 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 the 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.')Time and Space Complextity analysis
The total number of nodes in the first and second lists, m and n, respectively, determine the time complexity of the aforementioned solution, which is O(m + n). To store the first list’s nodes in a hash table, the programme needs O(m) additional space.
2.Making use of the Floyd’s Cycle Detection Algorithm
Making the first linked list circular by connecting its tail to its head is another strategy. Finding a loop in the second linked list is therefore the only issue left.
The aim is to use Floyd’s cycle detection approach to obtain a pointer to the loop node, and then use that loop node, let’s say k, to calculate the total number of nodes in the loop. After that, pick two pointers, one pointing to the head node and the other to the k’th node from the head. These pointers will eventually collide at the initial node of the loop if we concurrently move them at the same pace.
In C++, Java, and Python, the algorithm can be implemented as follows:
#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 list's front
void push(Node*& headRef, int data)
{
// create a new linked list node from the heap
Node* newNode = new Node;
newNode->data = data;
newNode->next = headRef;
headRef = newNode;
}
// Find the starting node of the loop in a 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 a 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, the linked list contains a cycle
if (slow == fast) {
return slow;
}
}
// return null if the 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 the previous pointer to the current node and
// move the main pointer to the next node
prev = curr;
curr = curr->next;
}
// create a cycle in the first list
if (prev) {
prev->next = first;
}
// now get a 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 the 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;
}
// 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 list's front
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 a 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 a 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, the linked list contains a cycle
if (slow == fast) {
return slow;
}
}
// return null if the 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 the previous pointer to the current node and
// move the main pointer to the next node
prev = curr;
curr = curr.next;
}
// create a cycle in the first list
if (prev != null) {
prev.next = first;
}
// now get a 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 the 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");
}
}
}
# 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 a 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 a 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, the 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 the previous pointer to the current node and
# move the main pointer to the next node
prev = curr
curr = curr.next
# create a cycle in the first list
if prev:
prev.next = first
# now get a 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 the 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.')Time and Space Complextity analysis
The time complexity of the above solution is O(m + n), where m and n are the total number of nodes in the first and second list, respectively.
3.Making use of various node counts
Finding the intersection point may also be done by comparing the number of nodes in the two lists. The goal is to move the larger list forward by k nodes, where k is the number of nodes that differ between the two lists. Once they cross, both lists should be moved at the same speed. The intersection point is the node at which both lists come together.
Python, C++, and Java all support the following implementation of this logic:
#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 list's front
void push(Node*& headRef, int data)
{
// create a new linked list node from the heap
Node* newNode = new Node;
newNode->data = data;
newNode->next = headRef;
headRef = newNode;
}
// Utility function to find the total number of nodes in a 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 don't meet
return nullptr;
}
// Function to find the intersection point of two linked lists
Node* findIntersection(Node* first, Node* second)
{
// get the difference in the 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 the 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;
}// 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 list's front
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 total number of nodes in a 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 don'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 the 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 the 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.");
}
}
}
# A Linked List Node
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
# Utility function to find the total number of nodes in a 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 the 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 the 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.')4.Using distance from intersection point
The total nodes in the first list plus the separation between the head of the second list and the intersection point equals the total nodes in the second list plus the separation between the head of the first list and the intersection point.
The plan is to use two pointers, x and y, which will initially refer to the first and second lists’ heads, respectively. Once they arrive at a common node, both points should go forward at the same rate. Send x to the top of the second list when it reaches its conclusion. Turn y to the top of the first list when it reaches its conclusion. The intersection node is the location where x and y converge.
The following is how the method may be used in
#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 list's front
void push(Node*& headRef, int data)
{
// create a new linked list node from the 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 a 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 the 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;
}
// 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 list's front
public static Node push(Node head, int data)
{
// create a new linked list node from the 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 a 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 the 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.");
}
}
}# 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 a 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 the 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.')Time and Space Complextity analysis
The above solution has a time complexity of O(m + n), where m and n are the total number of nodes in the first and second lists, respectively.