题面

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。

示例 1：

输入： head = [4,2,1,3] 输出：[1,2,3,4]

示例 2：

输入： head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]

示例 3：

输入： head = [] 输出：[]

提示：

链表中节点的数目在范围 [0, 5 104] 内

-105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

分析

如果空间复杂度为 $O(n)$ ，可以维护一个 dummy 节点，逐个遍历元素，并将其插入应该在的位置，其时间复杂度为 $O(n^2)$

如果是其奇数个节点，那么就找到正中间的节点，反转后面的节点；如果是偶数个，那么就找到中间两个中的第二个节点，正好将链表分成两半，这样通过递归排序左右两侧的链表，代码如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;

        if (head->next->next == nullptr && head->next->val < head->val) {
            ListNode* next = head->next;
            next->next = head;
            head->next = nullptr;
            return next;
        }
        ListNode *slow = head, *fast = head, *pre = head;
        while (fast != nullptr && fast->next != nullptr) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;
        ListNode* left = sortList(head);
        ListNode* right = sortList(slow);
        return mergeTwoLists(left, right);
    }
};

其时间复杂度为 $N\log n$ ，空间复杂度为 $\log n$
可以进一步优化空间复杂度吗？上述代码主要是由于堆栈导致的空间复杂度，可以使用迭代法来优化这部分空间消耗
可以看出，前面的归并算法是自顶向下计算，需要递归栈开销；现在改为自底向上计算，空间复杂度优化为 $O(1)$
具体算法：
- 遍历链表，获取链表长度 length
- 初始化步长 step=1
- 循环直到 step≥length
- 每轮循环，从链表头节点开始
- 分割出两段长为 step 的链表，合并，把合并后的链表插到新链表的末尾。重复该步骤，直到链表遍历完毕
- 把 step 扩大一倍。回到第 4 步

代码实现

class Solution {
    // 获取链表长度
    int getListLength(ListNode* head) {
        int length = 0;
        while (head) {
            length++;
            head = head->next;
        }
        return length;
    }

    // 分割链表
    // 如果链表长度 <= size，不做任何操作，返回空节点
    // 如果链表长度 > size，把链表的前 size 个节点分割出来（断开连接），并返回剩余链表的头节点
    ListNode* splitList(ListNode* head, int size) {
        // 先找到 next_head 的前一个节点
        ListNode* cur = head;
        for (int i = 0; i < size - 1 && cur; i++) {
            cur = cur->next;
        }

        // 如果链表长度 <= size
        if (cur == nullptr || cur->next == nullptr) {
            return nullptr; // 不做任何操作，返回空节点
        }

        ListNode* next_head = cur->next;
        cur->next = nullptr; // 断开 next_head 的前一个节点和 next_head 的连接
        return next_head;
    }

    // 21. 合并两个有序链表（双指针）
    // 返回合并后的链表的头节点和尾节点
    pair<ListNode*, ListNode*> mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy; // 用哨兵节点简化代码逻辑
        ListNode* cur = &dummy; // cur 指向新链表的末尾
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1; // 把 list1 加到新链表中
                list1 = list1->next;
            } else { // 注：相等的情况加哪个节点都是可以的
                cur->next = list2; // 把 list2 加到新链表中
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2; // 拼接剩余链表
        while (cur->next) {
            cur = cur->next;
        }
        // 循环结束后，cur 是合并后的链表的尾节点
        return {dummy.next, cur};
    }

public:
    ListNode* sortList(ListNode* head) {
        int length = getListLength(head); // 获取链表长度
        ListNode dummy(0, head); // 用哨兵节点简化代码逻辑
        // step 为步长，即参与合并的链表长度
        for (int step = 1; step < length; step *= 2) {
            ListNode* new_list_tail = &dummy; // 新链表的末尾
            ListNode* cur = dummy.next; // 每轮循环的起始节点
            while (cur) {
                // 从 cur 开始，分割出两段长为 step 的链表，头节点分别为 head1 和 head2
                ListNode* head1 = cur;
                ListNode* head2 = splitList(head1, step);
                cur = splitList(head2, step); // 下一轮循环的起始节点
                // 合并两段长为 step 的链表
                auto [head, tail] = mergeTwoLists(head1, head2);
                // 合并后的头节点 head，插到 new_list_tail 的后面
                new_list_tail->next = head;
                new_list_tail = tail; // tail 现在是新链表的末尾
            }
        }
        return dummy.next;
    }
};

排序链表

题面

分析

On this page

页面信息