Q8 Merge Sort for Linked List | Practice | GeeksforGeeks

//{ Driver Code Starts
//Initial Template for Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Node
{
    int data;
    Node next;
    Node(int key)
    {
        data = key;
        next = null;
    }
}

class Driverclass
{
    
    public static void main (String[] args) 
    {
        Scanner sc= new Scanner(System.in);
        int t = sc.nextInt();
        
        while(t-- > 0)
        {
            int n = sc.nextInt();
            Node head = new Node(sc.nextInt());
            Node tail = head;
            while(n-- > 1){
		        tail.next = new Node(sc.nextInt());
		        tail = tail.next;
		    }
		   
		      head = new Solution().mergeSort(head);
		     printList(head);
		    System.out.println();
        }
    }
    public static void printList(Node head)
    {
        if(head == null)
           return;
           
        Node temp = head;
        while(temp != null)
        {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
}



// } Driver Code Ends


//User function Template for Java
/*
class Node
{
    int data;
    Node next;
    Node(int key)
    {
        this.data = key;
        next = null;
    }
} */

class Solution
{
    //Function to sort the given linked list using Merge Sort.
    
    static Node mid(Node head){
        Node slow = head;
        Node fast = head;
        
        while(fast.next!= null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    static Node merge2SortedLL(Node head1, Node head2 ){
         Node dummy = new Node(-1);
         Node c1 = head1;
         Node c2 = head2;
         
         while(c1 != null && c2 != null){
             
             if(c1.data <= c2.data){
                 dummy.next = c1;
                 c1 = c1.next;
                 dummy = dummy.next;
             }
             else{
                 dummy.next = c2;
                 c2 = c2.next;
                 dummy = dummy.next;
             }
         }
         //attach the rest of the list which ever is not empty
         dummy.next =  c1 == null ? c2 :c1;
         
         return head1.data <= head2.data ? head1 : head2;
        
    }
    static Node mergeSort(Node head)
    {
        if(head == null || head.next == null)
        return head;
        
        //dividing LL in two parts from mid
        Node mid = mid(head);
        Node h = head;
        Node nh = mid.next;
        mid.next = null;
        
        Node l1 = mergeSort(h);
        Node l2 = mergeSort(nh);
        
        return merge2SortedLL(l1 , l2);
        
    }
}