148. Sort List

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

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4
Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

本题看起来只能用合并排序了。合并排序的思路主要是三步。首先将链表分为两部分；然后对两部分分别排序；最后将两链表合并为一个有序的链表并返回。

public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        //将链表分割为两部分
        ListNode prev = null, slow = head, fast = head;
        while(fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;//已将链表分为head和slow两部分
        //分别对两部分都进行排序
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        //将两链表合并并返回
        return merge(l1, l2);
    }

    //对两链表进行合并
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0), p = head;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if(l1 == null) {
            p.next = l2;
        }
        if(l2 == null) {
            p.next = l1;
        }
        return head.next;
    }

ListNode定义：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
 }