SortList.java

/**
 * 这题采用merge sort，可自顶向下或自底向上
 * 区别是自顶向下是递归的，需要额外的空间
 * 而自底向上不用
 * 时间复杂度都是O(nlgn)
 */
public class SortList {

    /**
     * 自顶向下
     */
    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;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        return merge(l1, l2);
    }

    ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), cur = dummy;
        for ( ; l1 != null && l2 != null; ) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }  else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dummy.next;
    }

    /**
     * 自底向上
     */
    public ListNode sortList2(ListNode head) {
        int size = 0;
        for (ListNode node = head; node != null; node = node.next, size++);
        ListNode dummy = new ListNode(0);
        ListNode left, right, cur, tail;
        for (int step = 1; step <= size; step *= 2) {
            for (cur = head, tail = dummy; cur != null; ) {
                left = cur;
                right = split(left, step);
                cur = split(right, step);
                tail = merge(left, right, tail);
            }
            head = dummy.next;
        }
        return dummy.next;
    }

    /**
     * 将l1和l2合并后挂在tail下，返回新的tail
     */
    ListNode merge(ListNode l1, ListNode l2, ListNode tail) {
        for ( ; l1 != null && l2 != null; ) {
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            }  else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = l1 != null ? l1 : l2;
        for ( ; tail.next != null; tail = tail.next);
        return tail;
    }

    /**
     * 从start开始取step个节点，返回下一个节点
     */
    private ListNode split(ListNode start, int step) {
        for (step--; start != null && step > 0; step--, start = start.next);
        if (start != null && start.next != null) {
            ListNode next = start.next;
            start.next = null;
            return next;
        }
        return null;
    }
}