# 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.

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

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

//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;
}else{
//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){
}
else{

//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

//When by mistake pass the reference of same Linked List

//select smallest element of given two list
//when first element of head2 list are smaller
}else{
//when first element of head1 list are smaller
}

temp=root;

//Find the smallest node of given two list
// modified node reference position
}else{
//modified node reference position
}
//Visit next node of new list
temp=temp->next;
}

//if head1 list are not NULL
}
//if head2 list are not NULL
}
//set second list is NULL

}
}

int main(){
//set node pointer value

return 0;
}``````

#### Output

``````head1
Linked List Elements :1  3  5  7  17
Linked List Elements :2  4  61  82
Linked List Elements :1  2  3  4  5  7  17  61  82
``````//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:
DoublyList();
void insert(int);
void display();
void merge_list(DoublyList*);
};
DoublyList::DoublyList(){
}//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;
}else{
//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(){
}
else{
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){

|| second==NULL
{
//That means given linked list are empty

//when second ==NULL , that means invalid object
return;
}else{
//get reference of nodes
//find first smallest element
if(temp->data > other->data)
{
}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
temp->next=self;
self->prev=temp;
}else if(other!=NULL){
//if second list are not NULL
temp->next=other;
other->prev=temp;
}
}
//Set NULL to second list head pointer
}
int main(){

//create objects

cout<<"Before Marge";
//display all node

cout<<"\nAfter Marge";
//display all node
return 0;
}``````

#### Output

``````Before Marge
Linked List : 1 3 5 7 17
Linked List : 2 4 64 82
After Marge
Linked List : 1 2 4 3 5 7 17 64 82
``````//Java program
//Sorted merge of two sorted doubly linked lists

static class Node{
int data;
Node next;
Node prev;
}
//Class constructors
}
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
else{
//find last node
while(temp.next!=null) temp=temp.next;
node.prev=temp;
temp.next=node;
}
}
//display all Linked List node value
public void display(){
while(temp!=null){
//display node value
System.out.print("  "+temp.data);
temp=temp.next;
}
}else{
}
}
//Combine two sorted Doubly Linked List into single from sorted order

|| second==null
{
//That means given linked list are empty

//when second ==null , that means invalid object
return;
}else{
//get reference of nodes
//find first smallest element
if(temp.data > other.data)
{
}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
temp.next=self;
self.prev=temp;
}else if(other!=null){
//if second list are not null
temp.next=other;
other.prev=temp;
}
}
//Set null to second list head pointer
}

public static void main(String[] args) {

System.out.println("Before Marge");
//display all node

System.out.println("\nAfter Marge");
//display all node
}
}``````

#### Output

``````Before Marge

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

Linked List Element :  1  2  4  3  5  7  17  64  82
``````
``````#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

def __init__(self):

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

#when empty list
else:
#find last node
while temp.next!=None:
temp=temp.next
temp.next=node
node.prev=temp

#view all node values
def display(self):
return

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

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

#when second ==None , that means invalid object
return
else:
#get reference of nodes
#find first smallest element
if(temp.data > other.data):
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
temp.next=current
current.prev=temp
elif(other!=None):
#if second list are not None
temp.next=other
other.prev=temp

#Set None to second list head pointer

def main():

print("Before Marge")
#display all node

print("After Marge")
#display all node

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

#### Output

``````Before Marge
1 3 5 7 17

2 4 64 82

After Marge
1 2 4 3 5 7 17 64 82

``````
``````//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 DoublyList(){
}
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
else{
//find last node
while(temp.next!=null) temp=temp.next;
node.prev=temp;
temp.next=node;
}
}
public void display(){
Console.Write("Empty List");
}else{
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){
|| second==null
{
//That means given linked list are empty

//when second ==null , that means invalid object
return;
}else{
//get reference of nodes
//find first smallest element
if(temp.data > other.data)
{
}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
temp.next=self;
self.prev=temp;
}else if(other!=null){
//if second list are not null
temp.next=other;
other.prev=temp;
}
}
//Set null to second list head pointer
}

static void Main()
{

Console.Write("Before Marge");
//display all node

Console.Write("\nAfter Marge");
//display all node
}
}``````

#### Output

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

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.