image.png

解法

自顶向下的归并，递归，会有O（logN）的空间复杂度

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return sort(head, null);
    }

    /**
     * 进行排序，但是尾部不取
     */
    public ListNode sort(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        // 快慢指针找中间点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != tail) {
            fast = fast.next;
            slow = slow.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        // 对两边的链表进行分别排序
        ListNode left = sort(head, slow);
        ListNode right = sort(slow, tail);
        // 进行merge操作
        ListNode dummyHead = new ListNode();
        ListNode temp = dummyHead;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        if (left != null) {
            temp.next = left;
        }
        if (right != null) {
            temp.next = right;
        }
        return dummyHead.next;
    }
}

自底向上，迭代解法，空间复杂度O（1）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }
        int len = 0;
        ListNode temp = head;
        while (temp != null) {
            len++;
            temp = temp.next;
        }

        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        // 每次扩大一倍步长，从下向上merge
        for (int subLen = 1; subLen < len; subLen = subLen * 2) {
            // pre后续过程后移。但dummyHead不移动，每次指向排好的头结点
            ListNode pre = dummyHead;
            ListNode cur = dummyHead.next;
            // 遍历整条链表，直到为null
            while (cur != null) {
                ListNode head1 = cur;
                for (int i = 1; i < subLen && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }

                ListNode head2 = cur.next;
                // 切断和head1之间的联系
                cur.next = null;
                cur = head2;
                for (int i = 1; i < subLen && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }

                // 保存head2的下一位元素，并切断联系
                ListNode next = null;
                if (cur != null) {
                    next = cur.next;
                    cur.next = null;
                }

                // 合并
                pre.next = merge(head1, head2);
                // 取合并链表的末尾
                while (pre.next != null) {
                    pre = pre.next;
                }
                // 接着合并
                cur = next;
            }
        }
        return dummyHead.next;
    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode dummyHead = new ListNode();
        ListNode temp = dummyHead;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        if (left != null) {
            temp.next = left;
        }
        if (right != null) {
            temp.next = right;
        }
        return dummyHead.next;
    }
}