本文共 2093 字，大约阅读时间需要 6 分钟。

题目地址：

排序一个链表。

由于链表无法random access，但用归并排序则不需要额外的空间（递归栈空间除外），所以可以用归并排序来解决。具体来说就是，先找到链表的中点，然后将链表断开，分别递归排序两部分，接着将两部分merge起来即可。代码如下：

public class Solution {       /**     * @param head: The head of linked list.     * @return: You should return the head of the sorted linked list, using constant space complexity.     */    public ListNode sortList(ListNode head) {           // write your code here        // base case是链表为空或者只有一个节点。注意借助数学归纳法来考虑递归出口是什么        if (head == null || head.next == null) {               return head;        }        ListNode mid = findMid(head);        ListNode secondHalf = mid.next;        mid.next = null;                ListNode l1 = sortList(head), l2 = sortList(secondHalf);        return merge(l1, l2);    }        private ListNode findMid(ListNode head) {           if (head == null) {               return null;        }                ListNode dummy = new ListNode(0);        dummy.next = head;        ListNode slow = dummy, fast = dummy;        while (fast != null && fast.next != null) {               slow = slow.next;            fast = fast.next.next;        }                return slow;    }        private ListNode merge(ListNode l1, ListNode l2) {           ListNode dummy = new ListNode(0), prev = dummy;        while (l1 != null || l2 != null) {               if (l1 == null) {                   prev.next = l2;                break;            } else if (l2 == null) {                   prev.next = l1;                break;            } else {                   if (l1.val <= l2.val) {                       prev.next = l1;                    l1 = l1.next;                } else {                       prev.next = l2;                    l2 = l2.next;                }                prev = prev.next;            }        }                return dummy.next;    }}class ListNode {       int val;    ListNode next;    ListNode(int x) {           val = x;    }}

时间复杂度$O(n\log n)$（找中点需要$O(n)$，所以$T(n)=O(n)+2T(\frac{n}{2})$，再由主定理即得），空间$O(\log n)$。