针对链表自底向上的递归排序

Question

老师您好，这是我针对leetcode148问题（题目要求在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序）的一个解答。我看了很多人的解答都用到了递归，如果递归的话那空间复杂度应该不满足要求才对，所以我使用了课上所讲的自底向上的归并排序来实现，可是感觉第二层循环的控制不是非常美观，也不太知道该怎么去优化。老师是否能给出这个问题的一个模板解法供我们参考。

class Solution148 {
    public static class ListNode {
        int val;
        ListNode next;

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

    public ListNode sortList(ListNode head) {
        //得到链表长度
        int n = 0;
        ListNode dup = head;
        while (dup != null) {
            n++;
            dup = dup.next;
        }

        //dh:用于返回的虚拟头节点;cur:用于遍历当前需要归并的链表；newHead:下一个需要归并的链表头；
        //lh、rh:用于合并的左右两个链表
        ListNode dh = new ListNode(-1);
        dh.next = head;
        ListNode cur;
        for (int sz = 1; sz < n; sz += sz) {
            ListNode pre = dh;
            ListNode newHead = dh.next;
            while (true) {
                cur = newHead;
                ListNode lh = cur;
                for (int i = 0; i < sz - 1 && cur != null; i++) cur = cur.next;
                if (cur == null || cur.next == null) {
                    pre.next = lh;
                    break;
                }
                ListNode rh = cur.next;
                cur.next = null;
                cur = rh;
                for (int i = 0; i < sz - 1 && cur != null; i++) cur = cur.next;
                if (cur == null) {
                    pre.next = mergeTwoList(lh, rh);
                    break;
                }
                newHead = cur.next;
                cur.next = null;
                pre.next = mergeTwoList(lh, rh);
                while (pre.next != null) {
                    pre = pre.next;
                }
            }
        }
        return dh.next;
    }

    //合并两个链表
    private ListNode mergeTwoList(ListNode l1, ListNode l2) {
        ListNode dh = new ListNode(-1);
        ListNode prev = dh;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;
        return dh.next;
    }
}

Answer 1

liuyubobobo 2019-11-22 15:29:55

赞！

是的，使用递归，空间复杂度，严格来说，应该是 logn 的。不过有的时候，在面试过程中，面试官（或者笔试中的题目）会明确表示忽视系统栈的空间分析：）

对链表进行归并排序，确实自顶向下的递归更好写一些。对于自底向上，我也实现过一个版本，仅供参考（C++）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0148-Sort-List/cpp-0148/main2.cpp

从代码行数上看，似乎你的代码更简洁：）

继续加油！：）

• 提问者 慕粉1548201684 #1

  好的，多谢老师