merge sort for linked list

PHOTO EMBED

Sun Dec 17 2023 04:02:13 GMT+0000 (Coordinated Universal Time)

Saved by @nistha_jnn #c++ 

//{ Driver Code Starts
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* next;
    Node(int x) {
        data = x;
        next = NULL;
    }
};


// } Driver Code Ends
/* Structure of the linked list node is as
struct Node 
{
    int data;
    struct Node* next;
    Node(int x) { data = x;  next = NULL; }
};
*/


class Solution{
  public:
    //Function to sort the given linked list using Merge Sort.
    Node* merge(Node* left,Node* right)
    {
        Node* ptr=NULL;
        if(!left)
        return right;
        if(!right)
        return left;
        if(left->data<right->data)
        {
            ptr=left;
            ptr->next=merge(left->next,right);
        }
        else
        {
            ptr=right;
            ptr->next=merge(left,right->next);
        }
        return ptr;
    }
    Node* middle(Node* head)
    {
        Node* slow=head;
        Node* fast=head->next;
        while(fast!=NULL and fast->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
    Node* mergeSort(Node* head)
    {
        if(!head or !head->next)
        return head;
        Node* left=head;
        Node* mid=middle(head);
        Node* right=mid->next;
        mid->next=NULL;
        left=mergeSort(left);
        right=mergeSort(right);
        Node* ans=merge(left,right);
        return ans;
    }
};


//{ Driver Code Starts.

void printList(Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

void push(struct Node** head_ref, int new_data) {
    Node* new_node = new Node(new_data);

    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main() {
    long test;
    cin >> test;
    while (test--) {
        struct Node* a = NULL;
        long n, tmp;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> tmp;
            push(&a, tmp);
        }
        Solution obj;
        a = obj.mergeSort(a);
        printList(a);
    }
    return 0;
}
// } Driver Code Ends
content_copyCOPY

gfg

https://www.geeksforgeeks.org/problems/sort-a-linked-list/1?itm_source=geeksforgeeks&itm_medium=article&itm_campaign=bottom_sticky_on_article