Different ways to find the merge point of two Lists
For the Singly Linked list, l1 and l2 pointed to by header1 and header2 as the header. The problem is to find the merge point of two lists. So, here we have to design a function such that, this function returns the node at which the two list merge. However, if there is no intersection point or merging point in both the lists, then this function will return null. The diagram below shows the visual representation of merge point of two linked lists.
![Find merge point of two lists in Java [Practical Examples]](https://www.golinuxcloud.com/wp-content/uploads/merge-point-of-two-lists-1-e1645122420563.jpg "Find merge point of two lists in Java [Practical Examples]")
The list below shows three different approach to find the merge point of two lists.
- Brute force approach
- Marking Visited Nodes
- Using HashSet
Method-1: Brute Force Approach
This is a traditional approach, where we will take two looping pointers that will search for the merge point of two lists. Here, pointer p will iterate over list l1 and q will iterate over the list l2. For each node in list l1, we will iterate over the list l2 and there by comparing the each node with current node in l1. At some point of time, we will get both the nodes to be equal marking as a merge point of two lists.
The code below has a function to find the merge point of two list. Also, it has a code to insert a node and traverse in the linked list.
class Node {
int data;
Node next;
Node(int val) {
next = null;
data = val;
}
}
public class Main {
public static void main(String[] args) {
Node header1;
Node header2;
// Inserting in Linked list 1
Node n1 = new Node(10);
header1 = n1;
Node n2 = new Node(20);
n1.next = n2;
Node n3 = new Node(30);
n2.next = n3;
Node n4 = new Node(40);
n3.next = n4;
Node n5 = new Node(50);
n4.next = n5;
// Inserting in Linked list 1
Node n6 = new Node(60);
header2 = n6;
Node n7 = new Node(70);
n6.next = n7;
Node n8 = new Node(80);
n7.next = n8;
Node n9 = new Node(90);
n8.next = n9;
Node n10 = new Node(100);
n9.next = n10;
// Creating merge point of two lists
n8.next = n3;
Main m = new Main();
// Traversing both the lists
m.traversal(header1);
m.traversal(header2);
// Calling mergepoint function to find the merge point of two lists
Node merge = m.mergepoint(header1, header2);
if (merge != null)
System.out.println("\nThe merge point of both the list is " + merge.data);
else
System.out.println("\nNo mergepoint found");
}
// Function to traverse a linked list
void traversal(Node h) {
Node p = h;
System.out.println();
while (p != null) {
System.out.print(p.data + " -> ");
p = p.next;
}
System.out.print("null");
}
// Function to find merge point of two lists
Node mergepoint(Node h1, Node h2) {
Node p = h1;
Node q = h2;
// Iterating over list 1
while (p != null) {
// Iterating over list 2
q = h2;
while (q != null) {
// Comparing the address of node p with node q
if (p == q) {
return p;
}
q = q.next;
}
// Moving to next node in list 1
p = p.next;
}
// return null if no merge point is found
return null;
}
}Output
10 -> 20 -> 30 -> 40 -> 50 -> null
60 -> 70 -> 80 -> 30 -> 40 -> 50 -> null
The merge point of both the list is 30
Method-2: Marking Node as visited
In this approach, we will have to change the structure of Node by adding an flag as extra field with the node. Here, we will first traverse all the node of list l1 and set its flag as 1 to mark it as visited. Thereafter, we will traverse the list l2 and check if the current node has flag 1 or not. If we find any node with the flag value as 1, it indicates that this is the merging point of two lists.
The code below has a function to find the merge point of two list. Also, it has a some lines of code to insert a node and traverse in the linked list.
class Node {
int data;
Node next;
int flag;
Node(int val) {
next = null;
data = val;
flag = 0;
}
}
public class Main {
public static void main(String[] args) {
Node header1;
Node header2;
// Inserting in Linked list 1
Node n1 = new Node(10);
header1 = n1;
Node n2 = new Node(20);
n1.next = n2;
Node n3 = new Node(30);
n2.next = n3;
Node n4 = new Node(40);
n3.next = n4;
Node n5 = new Node(50);
n4.next = n5;
// Inserting in Linked list 1
Node n6 = new Node(60);
header2 = n6;
Node n7 = new Node(70);
n6.next = n7;
Node n8 = new Node(80);
n7.next = n8;
Node n9 = new Node(90);
n8.next = n9;
Node n10 = new Node(100);
n9.next = n10;
// Creating merge point of two lists
n8.next = n3;
Main m = new Main();
// Traversing both the lists
m.traversal(header1);
m.traversal(header2);
// Calling mergepoint function to find the merge point of two lists
Node merge = m.mergepoint(header1, header2);
if (merge != null)
System.out.println("\nThe merge point of both the list is " + merge.data);
else
System.out.println("\nNo mergepoint found");
}
// Function to traverse a linked list
void traversal(Node h) {
Node p = h;
System.out.println();
while (p != null) {
System.out.print(p.data + " -> ");
p = p.next;
}
System.out.print("null");
}
// Function to find merge point of two lists
Node mergepoint(Node h1, Node h2) {
Node p = h1;
Node q = h2;
// Iterating over list 1 and marking flag as 1
int i = 0;
while (p != null) {
p.flag = 1;
p = p.next;
}
// Checking for the flag to be 1
while (q != null) {
if (q.flag == 1)
return q;
q = q.next;
}
// return null if no merge point is found
return null;
}
}Output
10 -> 20 -> 30 -> 40 -> 50 -> null
60 -> 70 -> 80 -> 30 -> 40 -> 50 -> null
The merge point of both the list is 30
Method-3: Using HashSet
In this approach, we will create an empty HashSet. Thereafter, we will traverse over a list l1 and adding the nodes of list l1 to the HashSet. We will then iterate over the list l2 and check if the current node in l2 is present in the HashSet using the contains() method of HashSet. Once, we obtain the node present in the HashSet indicates the merge point of two lists.
import java.util.HashSet;
class Node {
int data;
Node next;
int flag;
Node(int val) {
next = null;
data = val;
flag = 0;
}
}
public class Main {
public static void main(String[] args) {
Node header1;
Node header2;
// Inserting in Linked list 1
Node n1 = new Node(10);
header1 = n1;
Node n2 = new Node(20);
n1.next = n2;
Node n3 = new Node(30);
n2.next = n3;
Node n4 = new Node(40);
n3.next = n4;
Node n5 = new Node(50);
n4.next = n5;
// Inserting in Linked list 1
Node n6 = new Node(60);
header2 = n6;
Node n7 = new Node(70);
n6.next = n7;
Node n8 = new Node(80);
n7.next = n8;
Node n9 = new Node(90);
n8.next = n9;
Node n10 = new Node(100);
n9.next = n10;
// Creating merge point of two lists
n8.next = n3;
Main m = new Main();
// Traversing both the lists
m.traversal(header1);
m.traversal(header2);
// Calling mergepoint function to find the merge point of two lists
Node merge = m.mergepoint(header1, header2);
if (merge != null)
System.out.println("\nThe merge point of both the list is " + merge.data);
else
System.out.println("\nNo mergepoint found");
}
// Function to traverse a linked list
void traversal(Node h) {
Node p = h;
System.out.println();
while (p != null) {
System.out.print(p.data + " -> ");
p = p.next;
}
System.out.print("null");
}
// Function to find merge point of two lists
Node mergepoint(Node h1, Node h2) {
Node p = h1;
Node q = h2;
HashSet hs = new HashSet();
while (p != null) {
hs.add(p);
p = p.next;
}
while (q != null) {
if (hs.contains(q)) {
return q;
}
q = q.next;
}
return null;
}
}Output
10 -> 20 -> 30 -> 40 -> 50 -> null
60 -> 70 -> 80 -> 30 -> 40 -> 50 -> null
The merge point of both the list is 30
Summary
The knowledge of finding the merge point of two lists is very useful while working on real time applications. While, inserting the huge amount of data in the linked list, it may be possible that at some point of time both the lists are merging. In this type of situations, finding the merging point reduces lots of efforts in performing the further operations. In this tutorial, we covered three different approach to find the merge point of two lists in Java. As per the requirement of an application, we can choose an appropriate approach for searching. We learned in detail about this with an example.
All in all, this tutorial, covers everything that you need to know in order to have a clear view on how to find the merge point of two lists in Java.
References
