//{ 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); } }