LeetCode 热题 HOT 100 Java题解——148. 排序链表

LeetCode 热题 HOT 100 Java题解

• • 148. 排序链表

148. 排序链表

题目：

在 $O(nlogn)$ 时间复杂度和常数级空间复杂度下，对链表进行排序。

进阶：

你是否可以使用 O(1) 空间解决此题？

示例：

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

递归+归并

这种方法可以满足时间复杂度的要求，但是由于栈的开销，空间复杂度为$O(logn)$，并不满足要求。

核心就是找到每次要排序的中点（利用快慢指针），然后将两半链表进行归并排序（普通归并排序），这个是比较好理解的，难点是各种边界的判断。

class Solution {
    public ListNode findMid(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode fast = head.next, slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode ret = slow.next;
        slow.next = null;
        return ret;
    }
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(), p = dummy;
        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;
        }
        p.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode right = sortList(findMid(head));
        ListNode left = sortList(head);
        return merge(left, right);
    }
}

复杂度分析

• 时间复杂度：$O(nlogn)$

  每次归并复杂度为$O(n)$，递归调用复杂度为$O(logn)$，因此总复杂度为$0(nlogn)$。

• 空间复杂度：$O(logn)$

  递归栈深度$O(logn)$。

迭代+归并

按照规模从小到大进行归并排序，一开始规模为1，每相邻的两个节点进行一次归并，后面为每相邻的两个节点进行一次归并……。$cut$函数就是为了找到长度大小为$i$的链表头。逐步归并并扩大规模，直到$i>length$。

class Solution {
    public ListNode cut(ListNode head, int n) {
        while(head != null && n > 1) {
            head = head.next;
            n--;
        }
        if (head == null) return null;
        ListNode ret = head.next;
        head.next = null;
        return ret;
    }
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(), p = dummy;
        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;
        }
        p.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        int len = 0;
        ListNode p = head;
        while(p != null) {
            len++;
            p = p.next;
        }
        ListNode dummy = new ListNode();
        dummy.next = head;
        for (int i = 1; i < len; i *= 2) {
            ListNode cur = dummy.next;
            ListNode tail = dummy;
            while(cur != null) {
                ListNode left = cur;
                ListNode right = cut(left, i);
                cur = cut(right, i);
                tail.next = merge(left, right);
                while(tail.next != null) tail = tail.next;
            }
        }
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：$O(nlogn)$

  归并复杂度为$O(n)$，递归调用复杂度为$O(logn)$，因此总复杂度为$0(nlogn)$。

• 空间复杂度：$O(1)$

  常量级额外空间。

本文地址：https://blog.csdn.net/qq_20067165/article/details/109256833