How to merge two linked lists in Java

We will learn how to merge two Linked Lists in Java programming language with an example, algorithm, and a Java program.

In this program, we will merge two Linked List in an iterative fashion (by using while loop). This can be achieved by using recursion also but we won’t be doing that here.

We will not go for the definition. Let’s try to understand with this example.

A very popular example is that of the students in the cinema hall. Suppose there are 50 students going to watch a movie. Now the teacher taking them is unable to book 50 consecutive seats for them. So what the teacher does is that he books random seats in the theatre and after entering the hall he takes the ticket of the first student and tells him to take the ticket of the next student and to continue in the following manner. In this way, he will have the seat no. of the first student and when its time to go back he’ll simply go to the seat of the first student and take the ticket he has to the next seat no. and continue in this manner.

 

Merge two Linked Lists in Java

Let us understand this with two examples:

Example 1:
Input : head 1: 25->37->49
        head 2: 24->65->48 
Output : 24->28->37->44->49->65

Example 2:
Input : head 1: 1->3->5->7
        head 2: 2->4
Output : 1->2->3->4->5->7

As you can see the list will arrange itself in an ascending(low value to higher value) manner.

Algorithm:

In this program, we use two linked list which is already sorted. Then we will have to create a new Linked List and loop through both lists adding the later nodes.

  1.  Create two data filled and one empty Linked List.
  2. Check the first value of both Linked Lists.
  3. Whichever node from List 1 or List 2 is smaller, add it to the new empty list and move the pointer to the next node.
  4.  Repeat this process until you reach the end of the empty Linked List.

Java Program to merge two Linked Lists:

 

public class linkedlist
{
    public static class NodeA         //We are defining node 1 here
    {
        int data;       //data of node 1 here
        NodeA next;      //next refers to the address of the next node
        
    }
    public static class NodeB         //We are defining node 2 here
    {
        int data;
        NodeB next;
    }
    public static class NodeC
    {
        int data;
        NodeC next;
    }
    public static void main(String args[])
    {
        NodeA newnodeA1=new NodeA();    //here we are making objects of class NodeA
        NodeA newnodeA2=new NodeA();    //basically these are nodes of first linkedlist
        NodeA newnodeA3=new NodeA();    
        NodeA newnodeA4=new NodeA();    
        newnodeA1.data=1;
        newnodeA2.data=3;
        newnodeA3.data=5;
        newnodeA4.data=7;
        
        NodeB newnodeB1=new NodeB();    //here we are making objects of class NodeB
        NodeB newnodeB2=new NodeB();    //these are nodes of second linkedlist
        NodeB newnodeB3=new NodeB();    
        NodeB newnodeB4=new NodeB();    
        newnodeB1.data=2;
        newnodeB2.data=4;
        newnodeB3.data=6;
        newnodeB4.data=8;
        
        NodeC newnodeC1=new NodeC();    //here we are making objects of class NodeC
        NodeC newnodeC2=new NodeC();    //basically these are nodes of third linkedlist
        NodeC newnodeC3=new NodeC();    //notice that we are not entering any data into the third linked list
        NodeC newnodeC4=new NodeC();    //We are making objects twice in number to store both the arrays
        NodeC newnodeC5=new NodeC();
        NodeC newnodeC6=new NodeC();
        NodeC newnodeC7=new NodeC();
        NodeC newnodeC8=new NodeC();
        
        
        newnodeA1.next=newnodeA2;       //here we are linking the previous node to the next node of list A
        newnodeA2.next=newnodeA3;
        newnodeA3.next=newnodeA4;
        newnodeA4.next=null;
        
        newnodeB1.next=newnodeB2;       //here we are linking the previous node to the next node of list B
        newnodeB2.next=newnodeB3;
        newnodeB3.next=newnodeB4;
        newnodeB4.next=null;
        
        //Now both the linked lists are complete separate linked lists
        
        newnodeC1.next=newnodeC2;
        newnodeC2.next=newnodeC3;
        newnodeC3.next=newnodeC4;
        newnodeC4.next=newnodeC5;
        newnodeC5.next=newnodeC6;
        newnodeC6.next=newnodeC7;
        newnodeC7.next=newnodeC8;
        newnodeC8.next=null;
        
        //from here the merging starts
        NodeA currentnode1=newnodeA1;        //making temporary copied nodes with head of the linkedlists
        NodeB currentnode2=newnodeB1;
        NodeC currentnode3=newnodeC1;
        while(currentnode3.next!=null)      //loop will run until it reaches the end of linked list 3
        {
            if(currentnode1.data>currentnode2.data)     //data will be compared between two nodes and the smaller data will be inserted next
            {
                currentnode3.data=currentnode2.data;
                currentnode2=currentnode2.next;
                currentnode3=currentnode3.next;
                
            }
            else if(currentnode1.data<currentnode2.data)
            {
                currentnode3.data=currentnode1.data;
                currentnode1=currentnode1.next;
                currentnode3=currentnode3.next;
            }
            
        }
        
        //from here printing starts
        
        NodeC currentnode=newnodeC1;    //make a temporary node 
        System.out.println("The merged list is:");
        for (int i=1;i<=8;i++)
        {
            System.out.print(currentnode.data+" ");
            currentnode=currentnode.next;
        }
        
        
    }
}

The output of the above program :

How to merge two linked lists in Java

Also read:

Leave a Reply

Your email address will not be published. Required fields are marked *