单链表的排序问题
作者：Grey
原文地址：
题目链接
思路一：转换数组结合快速排序
将链表转换成数组，使用快速排序算法，然后把数组排序后的结果还原成链表。
时间复杂度 O(n*logn)，空间复杂度 O(n)。这个思路的核心就是快速排序算法，快速排序算法见如下博客荷兰国旗问题与快速排序算法说明，但是空间复杂度没有达到最优（最优解可以做到空间复杂度O(1)），完整代码如下：
class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } int size = 0; ListNode cur = head; while (cur != null) { size++; cur = cur.next; } ListNode[] nodes = new ListNode[size]; cur = head; int i = 0; while (cur != null) { nodes[i++] = cur; cur = cur.next; } sortArr(nodes); return arrToList(nodes); } private void sortArr(ListNode[] nodes) { p(nodes, 0, nodes.length - 1); } private void p(ListNode[] arr, int L, int R) { if (L >= R) { return; } swap(arr, L + (int) (Math.random() * (R - L + 1)), R); int[] equalArea = netherlandsFlag(arr, L, R); p(arr, L, equalArea[0] - 1); p(arr, equalArea[1] + 1, R); } private int[] netherlandsFlag(ListNode[] nodes, int L, int R) { if (L > R) { return new int[]{-1, -1}; } if (L == R) { return new int[]{L, R}; } int less = L - 1; int more = R; ListNode num = nodes[R]; for (int i = L; i < more; i++) { if (nodes[i].val < num.val) { swap(nodes, ++less, i); } else if (nodes[i].val > num.val) { swap(nodes, i--, --more); } } swap(nodes, R, more); return new int[]{less + 1, more}; } public void swap(ListNode[] nodes, int i, int j) { if (i != j) { ListNode t = nodes[i]; nodes[i] = nodes[j]; nodes[j] = t; } } public ListNode arrToList(ListNode[] nodes) { ListNode head = nodes[0]; ListNode cur = head; for (int i = 1; i < nodes.length; i++) { cur.next = nodes[i]; cur = nodes[i]; } cur.next = null; return head; } } 思路二：使用归并排序
本题可以利用归并排序算法，在时间复杂度同样为O(n*logn)的情况下，空间复杂度可以达到O(1)，本题参考了归并排序的迭代版本实现，归并排序算法的说明见如下博客与归并排序相关的一些问题。
归并排序的迭代方法，思路如下
设置一个步长，从 1 开始，1，2，4，8，16……2^n 方式递增
每次处理对应步长的链表区间范围内的排序。
步长超过或者等于链表长度，则整个链表排序完成。
比如原始链表为： 1->3->4->2->5->6->4->6->8
先设置步长为 1，链表分成如下区间
[0……1],[2……3],[4……5],[6……7],[8……8]
注：最后一组不够分，则单独作为一组处理。
将如上区间内部排好序，得到的排序后的链表为
1->3,2->4,5->6,4->6,8
然后设置步长为 2，链表分成如下区间
[0……3],[4……7],[8……8]。
然后将上述区间内部先排好序，得到链表为
1->2->3->4,4->5->6->6,8
然后设置步长为 4，链表分成如下区间
[0……7],[8……8]。
然后将上述区间内部先排好序，得到链表为
1->2->3->4->4->5->6->6,8
最后设置步长为 8，链表只有一个区间，直接排序，得到最后结果
1->2->3->4->4->5->6->6->8
完整代码如下
class Solution { public ListNode sortList(ListNode head) { int N = 0; ListNode cur = head; while (cur != null) { N++; cur = cur.next; } ListNode h = head; ListNode teamFirst = head; ListNode pre = null; int L = 1; while (L < N) { while (teamFirst != null) { ListNode[] hthtn = hthtn(teamFirst, L); ListNode[] mhmt = merge(hthtn[0], hthtn[1], hthtn[2], hthtn[3]); if (h == teamFirst) { h = mhmt[0]; pre = mhmt[1]; } else { pre.next = mhmt[0]; pre = mhmt[1]; } teamFirst = hthtn[4]; } teamFirst = h; pre = null; L <<= 1; } return h; } public ListNode[] hthtn(ListNode teamFirst, int len) { ListNode ls = teamFirst; ListNode le = teamFirst; ListNode rs = null; ListNode re = null; ListNode next = null; int p = 0; while (teamFirst != null) { // 之所以这里是小于等于，是因为这里可能不满足分组的个数（不足个数） if (p <= len - 1) { le = teamFirst; } if (p == len) { rs = teamFirst; } if (p > len - 1) { re = teamFirst; } if (p == (len << 1) - 1) { break; } p++; teamFirst = teamFirst.next; } if (le != null) { le.next = null; } if (re != null) { next = re.next; re.next = null; } return new ListNode[]{ls, le, rs, re, next}; } // 返回merge后的头和尾 // 注意边界考虑 public ListNode[] merge(ListNode h1, ListNode t1, ListNode h2, ListNode t2) { if (h2 == null) { return new ListNode[]{h1, t1}; } ListNode head = h1; ListNode tail = h1; ListNode c = null; ListNode pre = null; while (h1 != t1.next && h2 != t2.next) { if (h1.val > h2.val) { c = h2; h2 = h2.next; } else { c = h1; h1 = h1.next; } if (pre == null) { // 设置merge后的头节点,赋值给head // 后续就由pre去往下插入节点 pre = c; head = c; } else { pre.next = c; pre = c; } } // h1节点没越界 if (h1 != t1.next) { while (h1 != t1.next) { pre.next = h1; pre = pre.next; tail = h1; h1 = h1.next; } } else { while (h2 != t2.next) { pre.next = h2; pre = pre.next; tail = h2; h2 = h2.next; } } return new ListNode[]{head, tail}; } } 
