Find merge point of two lists in Java [Practical Examples]

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]

The list below shows three different approach to find the merge point of two lists.

Advertisement
  • 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.

Advertisement
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

HashSet Class

 

Didn't find what you were looking for? Perform a quick search across GoLinuxCloud

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation.

Buy GoLinuxCloud a Coffee

For any other feedbacks or questions you can either use the comments section or contact me form.

Thank You for your support!!

Leave a Comment

X