自顶向下

归并排序无序链表，自顶向下，故名思意就是将链表先切割成2部分，再切割成4部分，直到每个部分的元素为1个，此时是自然有序的，因为1个元素不用排序。

• 如何找到链表的最中间的节点？

那么不像数组，链表的话，不能通过访问索引arr.len/2的方式去直接获取，可以通过快慢指针。即快指针每次往前挪动2个，慢指针每次往前挪动1个。

那么假设快指针f和慢指针s初始时，都指向头节点。

• 奇数个节点的情况下，正好第3次时，f3到链表末尾，而s3到链表中点。
• 偶数个情况下，f3无法向前挪2个，因此只挪1个。而s不移动。

那么f先移动，如果发现后面下一个节点为空，则停止移动。如果下下一个节点不为空，则正常快进2慢进1。否则，快进1，慢不进。

大概可以写出伪码：

        // if the link listListNode f = head;ListNode s =head;while (f.next!=null){if (f.next.next!=null){f =  f.next.next;s = s.next;}else{f = f.next;}}

经过切割后， 第一个链表的区间为[head,s]，第二个链表的区间是[s.next,f]。

        public static ListNode mergeSort(ListNode head){if (head == null){return null;}// 如果只有一个元素，自然有序if (head.next == null){return head;}// 切割链表，一分为2ListNode f = head;ListNode s =head;while (f.next!=null){if (f.next.next!=null){f =  f.next.next;s = s.next;}else{f = f.next;}}// [head,s]  [s.next,f]ListNode l1 = head;   // 第一个链表头ListNode l2 = s.next; // 第二个链表头s.next = null;  // 将第一个链表和第二个链表断开// 继续切割ListNode orderedA= mergeSort(l1); ListNode orderedB = mergeSort(l2);// 合并两个有序链表ListNode merged  = merge(orderedA,orderedB);return merged;}

自底向上

通过合并排序将两个有序链表合并成一个是比较简单的。Leetcode 排序链表

关键是不用额外空间，怎么将[3,2], [2,6], [5,7] [1] 这些合并好的链表存储起来。其实只需要把局部有序集合再通过链表连起来即可。

引入一个指针dummy作为链表的头节点，prev作为这个链表的最后一个节点。[dummy, prev]之间的元素全是局部有序的。局部如何有序，取决于intv的长度。

比如当intv =1 时，先排序3和4，组成一个局部有序区间[3,4] 追加到prev后面，prev指向4;
再排序2和6时，组成一个局部区间[2,6], 追加到prev后面，prev指向6.

可以发现我们需要维护一个额外的指针cur,指向未处理的第一个节点5.

那么经过第一轮合并，dummy链表是两两有序的。那么下一轮，就可以开始合并两个元素的子链表了。

public static ListNode mergeSort(ListNode head){if (head == null){return null;}// 计算链表长度ListNode temp = head;int len = 0;while (temp!=null){len++;temp =temp.next;}// 空的链表头节点ListNode dummy = new ListNode();dummy.next =head;// 从最基础的自然有序，只有一个元素的链表直到长度为len/2. // 这里为什么是len/2? // 因为如果len是2的指数幂 2^n，那么合并为两个长度为2^(n-1)等长链表后, 排序完成了！// 如果不是2的指数幂，那么一长一短两个链表。长度为2^(n-1) 和 小于2^(n-1)链表合并，排序也完成了for (int i = 1; i < len; i= i<<1) {ListNode curr = dummy.next; // curr循环不变量，指向未处理的下个元素ListNode prev = dummy;      // prev循环不变量，指向已处理的最后一个元素。while (curr!=null){// 第一个链表ListNode fl = curr;  // 第一个链表头ListNode flTail = curr; // 第一个链表尾for (int j = 1; j < i && curr!=null; j++) {curr = curr.next;}// 防止出现空指针// case1: 比如最后链表剩下3个元素，但是i=4// 这个时候curr == null，不用做任何处理// case2: 没有在链表最后，curr指向了链表尾，那么将第一个链表和未处理的链表分离，先引入一个临时指针存储链表尾//  curr指向未处理的第一个元素。if (curr!=null){flTail =curr;curr = curr.next;flTail.next =null;}// 第二个链表ListNode sl =curr;ListNode slTail = curr;for (int j = 1; j < i && curr!=null; j++) {curr =curr.next;}if (curr!=null){slTail = curr;curr = curr.next;slTail.next =null;}// 合并两个有序链表ListNode merged = merge(fl,sl);// 把合并后的有序链表拼到prev后面prev.next = merged;// 维持prev 指向已处理的最后一个元素的性质。while (merged!=null){prev = merged;merged = merged.next;}}}return dummy.next;}// 合并两个有序的链表为一个有序的链表public static ListNode merge(ListNode a, ListNode b){if(a==null){return b;}if(b==null){return a;}// both link are not emptyListNode t1 = a;ListNode t2 = b;ListNode head = null;ListNode temp = null;while (t1!=null || t2!=null){if (head ==null){if (t1.val < t2.val){head  = t1;t1 = t1.next;}else{head  =t2;t2 = t2.next;}temp  = head;head.next =null;continue;}if (t1 == null){temp.next = t2;break;}if (t2 ==null){temp.next = t1;break;}if (t1.val < t2.val){temp.next = t1;t1 =t1.next;}else{temp.next  = t2;t2 = t2.next;}temp =temp.next;temp.next = null;}return head;}