Merge Sort for Doubly Linked List

Given a doubly linked list, write a function to sort the doubly linked list in increasing order using merge sort

Example

Time Complexity : O(nlogn)

Algorithm

mergeSort()

1. If head is NULL or there is only one element in the linked list then return

2. Else divide the linked list into two halves  ie, splitLL() splits list into list1 and list2

3. Sort the two halves     ie, recursively call mergeSort(list1), mergeSort(list2)

4. Merge the two sorted halves ie, mergeSortedList(list1,list2) does this job

Note : The above algorithm is same as mergeSort for singly linked list, but while merging two lists we need to modify prev pointer also

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LLNode{
	int data;
	LLNode *next;
  LLNode *prev;	
};
void display(LLNode**head);
//Prototypes
LLNode* mergeSortedLists(LLNode* list1, LLNode* list2);
void splitLL(LLNode* head, LLNode** list1, LLNode** list2);

//Main function, which will sort the lists
void mergeSort(LLNode** head)
{
  	LLNode* list1;
  	LLNode* list2;
  	/* Base case -- length 0 or 1 */
  	if ((*head == NULL) || ((*head)->next == NULL))
  	{
    	return;
  	}
 
  	// Split list(head) into 'list1' and 'list2' sublists 
  	splitLL(*head, &list1, &list2); 
 
  	/* Recursively sort the sublists */
  	mergeSort(&list1);
  	mergeSort(&list2);
  	//merge the two sorted lists together
  	*head = mergeSortedLists(list1, list2);
}
//Merge the two sorted lists
LLNode* mergeSortedLists(LLNode* list1, LLNode* list2)
{
  //display(&list1);
  //cout<<(list1->data);
  LLNode* result = NULL;
 
  /* Base cases */
  if (list1 == NULL)
     return(list2);
  else if (list2==NULL)
     return(list1);
 
  /* Pick either list1 or list2, and recur */
  if (list1->data <= list2->data)
  {
    list1->next = mergeSortedLists(list1->next,list2);
    list1->next->prev = list1;
    list1->prev = NULL;
    return list1;
  }
  else
  {
    list2->next = mergeSortedLists(list1,list2->next);
    list2->next->prev = list2;
    list2->prev = NULL;
    return list2;
  }
}
 
//split the nodes into two halves 
void splitLL(LLNode* head,
          LLNode** list1, LLNode** list2)
{
  LLNode* fast;
  LLNode* slow;
  if (head==NULL || head->next==NULL)
  {
    /* length < 2 cases */
    *list1 = head;
    *list2 = NULL;
  }
  else
  {
    slow = head;
    fast = head->next;
 
    // Move 'fast' two nodes, and move 'slow' one node //
    while (fast != NULL)
    {
      fast = fast->next;
      if (fast != NULL)
      {
        slow = slow->next;
        fast = fast->next;
      }
    }
 
    /* 'slow' is before the midpoint in the list, so split it in two
      at that point. */
    *list1 = head;
    *list2 = slow->next;
    slow->next = NULL;
  }
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
	LLNode*curr=new LLNode;
	//make a new node with this data and next pointing to NULL
	curr->data=dataToBeInserted;
	curr->next= curr->prev = NULL;

	if(*head==NULL) //if list is empty then set the current formed node as head of list
			*head=curr;
		
	else //make the next of the current node point to the present head and make the current node as the new head
		{
			curr->next=*head;
      (*head)->prev = curr;
			*head=curr;
		}
		
		//O(1) constant time
}

//Will print the list
void display(LLNode* head)
{
	LLNode*temp= head;
  
	while(head!=NULL) //till the list ends (NULL marks ending of list)
		{
			cout<<head->data<<" ->";
			temp = head;
			head = head->next; //move to next node
		}
  cout<<"Forward Traversal using next pointer"<<endl;   
  while(temp!=NULL) //till the list ends (NULL marks ending of list)
    {
      cout<<temp->data<<" ->";
      
      temp=temp->prev; //move to next node
    }  
    cout<<"Backward Traversal using prev pointer"<<endl;
		//O(number of nodes)
	cout<<endl;
}

int main() 
{    
	
	LLNode *head = NULL; //initial list has no elements
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);

	
	cout<<"\nCurrent List is :-\n";
	display(head);
	mergeSort(&head);
	cout<<"After doing Merge Sort"<<endl;
	display(head);
	return 0;
}
Try It

 


Next > < Prev
Scroll to Top