Sorted merge of two sorted doubly linked lists

Assume that we are two sorted doubly linked list, and we are combined this linked single one. The resultant of this linked list should be in a sorted order. For example.

First Sorted Doubly Linked List Second Sorted Doubly Linked List Sorted merge of two sorted doubly linked list

This last linked list are resultant of merge two sorted list. Before write an algorithm to of this problem consider following test cases.

1) When given anyone linked list are empty then we cannot merge linked list.

2) There is possible to compare both linked list are not same number of nodes. but the sequence of both linked list is ascending order.

head1 : 1->9->11->NULL
head2 : 4->5->9->18->NULL
resultant head1: 1->4->5->9->9->11->18

3) There are possible to exist repeated element in linked list. See above example here 9 is exist in a both linked list.

Here given code implementation process.

//C Program
//Sorted merge of two sorted doubly linked lists
#include <stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
  int data;
  struct Node*next;
  struct Node*prev;
};

//function prototype
void insert(struct Node**,int);
void display(struct Node*);

//insert Node element of end of linked list
void insert(struct Node**head,int value){

  //Create a dynamic node
  struct Node*node=(struct Node*)malloc(sizeof(struct Node));
  if(node==NULL){
    printf("Memory overflow\n");
  }else{
    //set data value
    node->data=value;
    node->next=NULL;
    node->prev=NULL;
    if(*head==NULL){
      *head=node;
    }else{
        struct Node*temp=*head;
        //find last node
        while(temp!=NULL && temp->next!=NULL){
          temp=temp->next;
        }
        //add new node to last positions
        temp->next=node;
        node->prev=temp;
       
    }
  }
}
//display element of Node
void display(struct Node*temp){
  
  if(temp==NULL){
    printf("Empty linked list");
  }
  else{
    printf("\nLinked List Elements :");
  
    //Traverse doubly linked list from front to rear
    while(temp!=NULL){
      //print node value
      printf("%d  ",temp->data);
      temp=temp->next;
    }
  }

}
//Combine two sorted Doubly Linked List into single  from sorted order
void merge_list(struct Node**head1,struct Node**head2){

  if(*head1!=NULL && *head2!=NULL){
    //When by mistake pass the reference of same Linked List
    if(*head1==*head2) return;

    struct Node*root=*head1,*temp=NULL;

    //select smallest element of given two list
    if(root->data > (*head2)->data){
      //when first element of head2 list are smaller
      root=*head2;
      *head2=root->next;
    }else{
      //when first element of head1 list are smaller
      *head1=root->next;
    }

    temp=root;

    while(*head1 !=NULL && *head2 !=NULL){
      //Find the smallest node of given two list
      if((*head1)->data < (*head2)->data){
        //When head1 is smaller 
        // modified node reference position
        temp->next=(*head1);
        (*head1)->prev=temp;
        (*head1)=(*head1)->next;
      }else{
        //When head1 is smaller 
        //modified node reference position
        temp->next=(*head2);
        (*head2)->prev=temp;
        (*head2)=(*head2)->next;
      }
      //Visit next node of new list
      temp=temp->next;
    }

    if(*head1!=NULL){
      //if head1 list are not NULL
      //then add remaining elements
      temp->next=*head1;
      (*head1)->prev=temp;
    }
    else if(*head2!=NULL){
      //if head2 list are not NULL
      //then add remaining elements
      temp->next=*head2;
      (*head2)->prev=temp;
    }
    //make new list head
    *head1=root;
    //set second list is NULL
    *head2=NULL;

  }
}

int main(){
  //set node pointer value
  struct Node*head1=NULL,*head2=NULL;
  //Insert element of linked list
  //head1
  insert(&head1,1);
  insert(&head1,3);
  insert(&head1,5);
  insert(&head1,7);
  insert(&head1,17);
  //head2
  insert(&head2,2);
  insert(&head2,4);
  insert(&head2,61);
  insert(&head2,82);

  printf("\nhead1");
  display(head1);
  
  printf("\nhead2");
  display(head2);
  merge_list(&head1,&head2);
  printf("\nhead1");
  display(head1);
  printf("\nhead2  ");
  display(head2);
  return 0;
}

Output

head1
Linked List Elements :1  3  5  7  17  
head2
Linked List Elements :2  4  61  82  
head1
Linked List Elements :1  2  3  4  5  7  17  61  82  
head2  Empty linked list
//C++ Program 
//Sorted merge of two sorted doubly linked lists
#include<iostream>
using namespace std;

//create structure
struct Node{
    int data;
    Node*next;
    Node*prev;
};
class DoublyList{
 
  public:
    Node*head;//head node
    DoublyList();
    void insert(int);
    void display();
    void merge_list(DoublyList*);
};
DoublyList::DoublyList(){
  head=NULL;
}//insert a linked list Node element
void DoublyList:: insert(int value){
    //Create a dynamic node
    Node*node=new Node;
    if(node==NULL){
        cout<<"Memory overflow\n";
    }
    else{
        //set data value
        node->data=value;
        node->next=NULL;
        node->prev=NULL;
        if(head==NULL){
          head=node;
        }else{
            Node*temp=head;
            //find last node
            while(temp!=NULL && temp->next!=NULL){
              temp=temp->next;
            }
            //add new node to last positions
            temp->next=node;
            node->prev=temp;
           
        }
    }
}
//display all node value in linked list
void DoublyList:: display(){
  if(head==NULL){
    cout<<"\nEmpty linked list"<<endl;
  }
  else{
    Node*temp=head;
    cout<<"\nLinked List : ";
    while(temp!=NULL){
      //print node value
      cout<<temp->data<<" ";
      temp=temp->next;
    }
  }

}
//Combine two sorted Doubly Linked List into single  from sorted order
void DoublyList:: merge_list(DoublyList *second){

  if(head==NULL
    || second==NULL
    || second->head==NULL 
    || head==second->head)
  {
    //(head==NULL or second->head==NULL)
    //That means given linked list are empty

    //when second ==NULL , that means invalid object
    //when head==second->head, means same linked list object
    return;
  }else{
    //get reference of nodes
    Node *temp=head,*self=head,*other=second->head;
    //find first smallest element
    if(temp->data > other->data)
    {
        head=other;
        other=head->next;
    }else{
      self=self->next;
    }
    while(self != NULL && other !=NULL){
      //Find the smallest node of given two list
      if(self->data > other->data){
         //When second list node is smaller 
        // modified node reference position
        temp->next=other;
        other->prev=temp;
        other=other->next;
      }else{
        //When first list node is smaller 
        // modified node reference position
        temp->next=self;
        self->prev=temp;
        self=self->next;
      }
      temp=temp->next;
    }
    if(self!=NULL){
      //if first list are not NULL
      //then add remaining elements
      temp->next=self;
      self->prev=temp;
    }else if(other!=NULL){
      //if second list are not NULL
      //then add remaining elements
      temp->next=other;
      other->prev=temp;
    }
  }
  //Set NULL to second list head pointer
  second->head=NULL;
}
int main(){
 
  //create objects
  DoublyList head1;
  DoublyList head2;
  //insert first linked list elements
  head1.insert(1);
  head1.insert(3);
  head1.insert(5);
  head1.insert(7);
  head1.insert(17);

  //insert second linked list elements
  head2.insert(2);
  head2.insert(4);
  head2.insert(64);
  head2.insert(82);

  cout<<"Before Marge";
  //display all node
  cout<<"\nhead1 :";
  head1.display();
  cout<<"\nhead2 :";
  head2.display();
  
  cout<<"\nAfter Marge";
  head1.merge_list(&head2);
  //display all node
  cout<<"\nhead1 :";
  head1.display();
  cout<<"\nhead2 :";
  head2.display();
  return 0;
}

Output

Before Marge
head1 :
Linked List : 1 3 5 7 17 
head2 :
Linked List : 2 4 64 82 
After Marge
head1 :
Linked List : 1 2 4 3 5 7 17 64 82 
head2 :
Empty linked list
//Java program
//Sorted merge of two sorted doubly linked lists
public class LinkedList{

  static class Node{
    int data;
    Node next;
    Node prev;
  }
    //head of linked list
  public Node head;
    //Class constructors
  LinkedList(){
    head=null;
  } 
    //add newly created node at End of linked list
  public void insert(int value){
        //Create a dynamic node
    Node node=new Node();
        //add node value and pointer value
    node.data=value;
    node.next=null;
    node.prev=null;
        //when no element
    if(head==null) head=node;
    else{
      Node temp=head;
          //find last node
      while(temp.next!=null) temp=temp.next;
          //add node
      node.prev=temp;
      temp.next=node;
    }
  }
    //display all Linked List node value
  public void display(){
    if(head!=null){
      System.out.print(" Linked List Element :");
      Node temp=head;
      while(temp!=null){
                //display node value
        System.out.print("  "+temp.data);
        temp=temp.next;
      }
    }else{
      System.out.println("Empty Linked list"); 
    }
  }
  //Combine two sorted Doubly Linked List into single from sorted order

  public void mergeList(LinkedList second){
    if(head==null
      || second==null
      || second.head==null 
      || head==second.head)
    {
        //(head==null or second.head==null)
        //That means given linked list are empty

        //when second ==null , that means invalid object
        //when head==second.head, means same linked list object
      return;
    }else{
        //get reference of nodes
      Node  temp=head, self=head, other=second.head;
        //find first smallest element
      if(temp.data > other.data)
      {
        head=other;
        other=head.next;
      }else{
        self=self.next;
      }
      while(self != null && other !=null){
            //Find the smallest node of given two list
        if(self.data > other.data){
              //When second list node is smaller 
              // modified node reference position
          temp.next=other;
          other.prev=temp;
          other=other.next;
        }else{
              //When first list node is smaller 
              // modified node reference position
          temp.next=self;
          self.prev=temp;
          self=self.next;
        }
        temp=temp.next;
      }
      if(self!=null){
            //if first list are not null
            //then add remaining elements
        temp.next=self;
        self.prev=temp;
      }else if(other!=null){
            //if second list are not null
            //then add remaining elements
        temp.next=other;
        other.prev=temp;
      }
    }
      //Set null to second list head pointer
    second.head=null;
  }


  public static void main(String[] args) {

    LinkedList head1=new LinkedList();
    LinkedList head2=new LinkedList();

    //insert first linked list elements
    head1.insert(1);
    head1.insert(3);
    head1.insert(5);
    head1.insert(7);
    head1.insert(17);

    //insert second linked list elements
    head2.insert(2);
    head2.insert(4);
    head2.insert(64);
    head2.insert(82);

    System.out.println("Before Marge");
    //display all node
    System.out.println("\nhead1 :");
    head1.display();
    System.out.println("\nhead2 :");
    head2.display();

    System.out.println("\nAfter Marge");
    head1.mergeList(head2);
    //display all node
    System.out.println("\nhead1 :");
    head1.display();
    System.out.println("\nhead2 :");
    head2.display();
  }
}

Output

Before Marge

head1 :
 Linked List Element :  1  3  5  7  17
head2 :
 Linked List Element :  2  4  64  82
After Marge

head1 :
 Linked List Element :  1  2  4  3  5  7  17  64  82
head2 :
Empty Linked list
#Python Program
#Sorted merge of two sorted doubly linked lists

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
        self.prev=None

#create class LinkedList    
class LinkedList:
    def __init__(self):
        #set initial head value
        self.head=None


    #insert new node to end of Linked List  
    def insert(self,data):
        #make a new node
        node=Node(data)

        if(self.head==None):
            #when empty list
            self.head=node
        else:
            temp=self.head
            #find last node
            while temp.next!=None:
                temp=temp.next
            #add node    
            temp.next=node
            node.prev=temp

     

    #view all node values    
    def display(self):
        if(self.head==None):
            print("Empty Linked List  ")
            return
        temp=self.head
        print("Linked List Elements : ")

        while(temp!=None):
            #print node value
            print(temp.data,end=" ")
            temp=temp.next
        print("\n")

    def mergeList(self,second):
        if(self.head==None
            or second==None
            or second.head==None 
            or self.head==second.head):
            #(head==None or second.head==None)
            #That means given linked list are empty

            #when second ==None , that means invalid object
            #when head==second.head, means same linked list object
            return
        else:
            #get reference of nodes
            temp=self.head
            current=self.head
            other=second.head
            #find first smallest element
            if(temp.data > other.data):
                self.head=other
                other=head.next
            else:
                current=current.next
            
            while(current != None and other !=None):
                #Find the smallest node of given two list
                if(current.data > other.data):
                    #When second list node is smaller 
                    # modified node reference position
                    temp.next=other
                    other.prev=temp
                    other=other.next
                else:
                    #When first list node is smaller 
                    # modified node reference position
                    temp.next=current
                    current.prev=temp
                    current=current.next
                
                temp=temp.next
            
            if(current!=None):
                #if first list are not None
                #then add remaining elements
                temp.next=current
                current.prev=temp
            elif(other!=None):
                #if second list are not None
                #then add remaining elements
                temp.next=other
                other.prev=temp
            
        
          #Set None to second list head pointer
        second.head=None
    

def main():
    #create object of LinkedList
    head1=LinkedList()
    head2=LinkedList()
    #insert first linked list elements
    head1.insert(1)
    head1.insert(3)
    head1.insert(5)
    head1.insert(7)
    head1.insert(17)

    #insert second linked list elements
    head2.insert(2)
    head2.insert(4)
    head2.insert(64)
    head2.insert(82)

    print("Before Marge")
    #display all node
    print("head1 :")
    head1.display()
    print("head2 :")
    head2.display()

    print("After Marge")
    head1.mergeList(head2)
    #display all node
    print("head1 :")
    head1.display()
    print("head2 :")
    head2.display()
    

if(__name__=="__main__"):
    main()

Output

Before Marge
head1 :
Linked List Elements : 
1 3 5 7 17 

head2 :
Linked List Elements : 
2 4 64 82 

After Marge
head1 :
Linked List Elements : 
1 2 4 3 5 7 17 64 82 

head2 :
Empty Linked List  
//C# DoublyList
//Sorted merge of two sorted doubly linked lists
using System;
public class Node{
  public  int data;
  public  Node next;
  public Node prev;
}
class DoublyList
{
  public Node head;
  public DoublyList(){
    head=null;
  }
  public void insert(int data){
    //Create a dynamic node
    Node node=new Node();
    //add node value and pointer value
    node.data=data;
    node.next=null;
    node.prev=null;
    //when no element
    if(head==null) head=node;
    else{
      Node temp=head;
      //find last node
      while(temp.next!=null) temp=temp.next;
      //add node
      node.prev=temp;
      temp.next=node;
    }
  }
  //display linked list node value
  public void display(){
    if(head==null){
      Console.Write("Empty List");
    }else{
      Console.Write("Linked List :");
      Node temp=head;
      while(temp!=null){
        //display node value
        Console.Write("  {0}",temp.data);
        temp=temp.next;
      }

    }
  }
  //Combine two sorted Doubly Linked List into single from sorted order

  public void mergeList(DoublyList second){
    if(head==null
      || second==null
      || second.head==null 
      || head==second.head)
    {
      //(head==null or second.head==null)
      //That means given linked list are empty

      //when second ==null , that means invalid object
      //when head==second.head, means same linked list object
      return;
    }else{
      //get reference of nodes
      Node  temp=head, self=head, other=second.head;
      //find first smallest element
      if(temp.data > other.data)
      {
        head=other;
        other=head.next;
      }else{
        self=self.next;
      }
      while(self != null && other !=null){
        //Find the smallest node of given two list
        if(self.data > other.data){
          //When second list node is smaller 
          // modified node reference position
          temp.next=other;
          other.prev=temp;
          other=other.next;
        }else{
          //When first list node is smaller 
          // modified node reference position
          temp.next=self;
          self.prev=temp;
          self=self.next;
        }
        temp=temp.next;
      }
      if(self!=null){
        //if first list are not null
        //then add remaining elements
        temp.next=self;
        self.prev=temp;
      }else if(other!=null){
        //if second list are not null
        //then add remaining elements
        temp.next=other;
        other.prev=temp;
      }
    }
    //Set null to second list head pointer
    second.head=null;
  }

  static void Main()
  {
    DoublyList head1=new DoublyList();
    DoublyList head2=new DoublyList();
    //insert first linked list elements
    head1.insert(1);
    head1.insert(3);
    head1.insert(5);
    head1.insert(7);
    head1.insert(17);

    //insert second linked list elements
    head2.insert(2);
    head2.insert(4);
    head2.insert(64);
    head2.insert(82);

    Console.Write("Before Marge");
    //display all node
    Console.Write("\nhead1 :");
    head1.display();
    Console.Write("\nhead2 :");
    head2.display();

    Console.Write("\nAfter Marge");
    head1.mergeList(head2);
    //display all node
    Console.Write("\nhead1 :");
    head1.display();
    Console.Write("\nhead2 : ");
    head2.display();
  }
}

Output

Before Marge
head1 :Linked List :  1  3  5  7  17
head2 :Linked List :  2  4  64  82
After Marge
head1 :Linked List :  1  2  4  3  5  7  17  64  82
head2 : Empty List


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved