Sort a linked list in O(n log n) time using constant space complexity.

 1 /** 2  * Definition for singly-linked list. 3  * class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode sortList(ListNode head) {14         if (head == null) {15             return null;16         }17         return mergesort(head);18     }19     20     public ListNode mergesort(ListNode head) {21         if (head.next == null) return head;22         ListNode dummy = new ListNode(0);23         dummy.next = head;24         ListNode current = dummy;25         ListNode runner = dummy;26         while (runner != null && runner.next != null) {27             runner = runner.next.next;28             current = current.next;29         }30         ListNode newhead = current.next;31         current.next = null;32         ListNode head1 = mergesort(head);33         ListNode head2 = mergesort(newhead);34         return merge(head1, head2);35     }36     37     public ListNode merge(ListNode l1, ListNode l2) {38         ListNode dummyNode = new ListNode(0);39         ListNode currentNode = dummyNode;40         41         while (l1!=null || l2!=null) {42             if (l1!=null && l2!=null) {43                 if (l1.val > l2.val) {44                     currentNode.next = l2;45                     l2 = l2.next;46                 }47                 else {48                     currentNode.next = l1;49                     l1 = l1.next;50                 }51             }52             else {53                 if (l1 != null) {54                     currentNode.next = l1;55                     l1 = l1.next;56                 }57                 else {58                     currentNode.next = l2;59                     l2 = l2.next;60                 }61             }62             currentNode = currentNode.next;63         }64         return dummyNode.next;65     }66 }