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