Merge Sort On Linked List | Data Structure in C++

Introduction:

Merge Sort: Merge Sort is basically a sorting technique to sort the data. so basically we use it with array.but today we will apply it in linked list.

Problem Statement:

We have given a linked list, and we have to sort it using any sorting technique.

eg: Input: 1->4->5->2->NULL

      Output: 1->2->4->5->NULL

Solution:

To apply merge sort on linked list, we will maintain three function.

1.we should have a function to find the middle of the linked list.(findMid function)

2.we should have a function which will break the linked list into two parts.(mergeSort function)

3.we should have a function which will merge two list in sorted order.(merge function)

Important Point: first of all we have to find the tail of the list. and then we will pass head as well as tail to our merge sort function. kindly go through the code. you will understand each function easily.

Full Code: Merge Sort In C++ On Linked List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode *findMid(ListNode* l1, ListNode* l2){
        ListNode* slow = l1;
        ListNode* fast = l1;
        while(fast!=l2 && fast->next!=l2){
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
   
    ListNode *merge(ListNode *l1, ListNode *l2){
        ListNode *newlist=NULL;
        ListNode *temp;
       
        while(l1!=NULL && l2!=NULL){
            if(l1->val <= l2->val){
                if(newlist==NULL){
                   newlist = new ListNode();
                   newlist->val = l1->val;
                   newlist->next=NULL;
                    temp=newlist;
                }
                else{
                    ListNode *temp1 = new ListNode();
                    temp1->val=l1->val;
                    temp1->next=NULL;
                    temp->next=temp1;
                    temp=temp1;
                }
                l1=l1->next;
            }
            else{
                if(newlist==NULL){
                   newlist = new ListNode();
                   newlist->val = l2->val;
                   newlist->next=NULL;
                    temp=newlist;
                }
                else{
                    ListNode *temp1 = new ListNode();
                    temp1->val=l2->val;
                    temp1->next=NULL;
                    temp->next=temp1;
                    temp=temp1;
                }
                l2=l2->next;
            }
        }
        while(l1!=NULL){
            ListNode *temp1 = new ListNode();
                    temp1->val=l1->val;
                    temp1->next=NULL;
                    temp->next=temp1;
                    temp=temp1;
                    l1=l1->next;
        }
        while(l2!=NULL){
            ListNode *temp1 = new ListNode();
                    temp1->val=l2->val;
                    temp1->next=NULL;
                    temp->next=temp1;
                    temp=temp1;
                    l2=l2->next;
        }
        return newlist;
           
    }
   
    ListNode *mergeSort(ListNode* left, ListNode *right){
        if(left==right){
            ListNode* temp3 = new ListNode();
            temp3->val=left->val;
            temp3->next=NULL;
            return temp3;
        }
        ListNode* mid = findMid(left,right);
        ListNode* ls = mergeSort(left,mid);
        ListNode* rs = mergeSort(mid->next,right);
        ListNode* nl = merge(ls,rs);
        ListNode* print = nl;
        return nl; 
    }
   
    ListNode* sortList(ListNode* head) {
        if(head==NULL || head->next==NULL)
            return head;
        ListNode* tail = head;
        while(tail->next!=NULL){
            tail=tail->next;
        }
        ListNode *ans = mergeSort(head,tail);
        return ans;
       
           
    }
};

Conclusion:

we are doing all thing, which we do when we perform merge sort on array. first thing is you must know about first node and last node of the list. after that you will find the mid of the list. then call mergesort function on both halves and so on. so there is nothing new except syntax.