Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

Symmetric Tree | Interview Problem

Introduction: In this tutorial we are going to solve a good question which will clear your doubts on how BFS or level order traversal is useful to solve binary tree problems. this is basically a question from Leetcode, and it is really very good problem to practice BFS. Problem Statement: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: But the following [1,2,2,null,3,null,3] is not: Link : Leetcode Link please make binary tree on paper by the given array above. and you will get a clear picture of the problem. what we are going to do in this problem. Solution: As we know we are going to apply BFS to solve this problem. actually you have to just get one thing to solve this problem. we will perform BFS, but with little change or modification. So first we will store the root->val in a vector or array of the left subtree. and during this we will first insert left child and then ...
Post a Comment
Read more

Construct Binary Tree from preorder and inorder | Data Structure

Introduction: In this tutorial we are going to see how we can construct the binary tree from given preorder and inorder. Prerequisites: you should know about binary tree traversal and on paper you can draw binary tree from given preorder and inorder traversal. Inorder:left->root->right; Preorder:root->left->right; Problem Statement: we have given two arrays. one for preorder and another for inorder. by using these two array we have to built a binary tree. eg: preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] solution: Solution: We will follow recursive approach to solve this question.let's discuss how we can solve it. Trick: In the given preorder the very first element will be the root of the tree. then we will find root element in inorder also. and we know in inorder traversal we have left part then root and then right part of the tree. by using preorder we can get the root of the main tree and by using inorder and root we can get the left part and right part of the...
Post a Comment
Read more

Linked List Data Structure | Creation and Traversal

Introduction: In this tutorial we will create our linked list. Before writing code let's understand key words related to linked list: 1. Head:    first node of the linked list is called the head of the list. and this node is most important. 2.Tail:       last node is called the tail of the list which must points to  null.            step1: For creating the list first of all let's declare the structure of Nodes of the list: struct Node{ int val; struct Node *next; } step2: write main function: int main(){     int n;     cout<<"enter the number of Nodes:";     cin>>n;     struct Node* head = NULL;     struct Node* temp;     int m;     while(n--){         cout<<"enter the data into nodes:";         cin>>m;    ...
1 comment
Read more