LeetCode hot 力扣热题100 排序链表

归并忘了 直接抄！

class Solution { // 定义一个 Solution 类，包含链表排序的相关方法。
    // 使用快慢指针找到链表的中间节点，并断开链表为两部分
    ListNode* middleNode(ListNode* head) { 
        ListNode* slow = head; // 慢指针 slow 初始化为链表头节点
        ListNode* fast = head; // 快指针 fast 初始化为链表头节点
        while (fast->next && fast->next->next) { // 当 fast 指针还能向前走两步时循环
            slow = slow->next; // slow 每次向前移动一步
            fast = fast->next->next; // fast 每次向前移动两步
        }
        ListNode* mid = slow->next; // 找到中间节点的下一节点，将其作为右半部分的头节点
        slow->next = nullptr; // 将左半部分的最后一个节点的 next 指针置为 nullptr，断开链表
        return mid; // 返回右半部分的头节点 mid
    }

    // 合并两个有序链表，返回合并后的链表头节点
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy; // 定义一个哨兵节点，简化合并逻辑
        ListNode* cur = &dummy; // cur 用于构建新链表，初始指向哨兵节点
        while (list1 && list2) { // 当两个链表都不为空时进行合并
            if (list1->val < list2->val) { // 如果 list1 的当前值小于 list2 的当前值
                cur->next = list1; // 将 list1 的节点加入新链表
                list1 = list1->next; // list1 指针向后移动
            } else { // 否则，将 list2 的节点加入新链表
                cur->next = list2;
                list2 = list2->next; // list2 指针向后移动
            }
            cur = cur->next; // cur 指针向后移动
        }
        cur->next = list1 ? list1 : list2; // 将剩余的非空链表直接接到新链表末尾
        return dummy.next; // 返回新链表的头节点（哨兵节点的下一个节点）
    }

public:
    // 链表归并排序的主函数
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) { // 如果链表为空或只有一个节点，直接返回
            return head;
        }
        ListNode* head2 = middleNode(head); // 使用 middleNode 函数分割链表，head2 是右半部分的头节点
        head = sortList(head); // 递归地对左半部分链表排序
        head2 = sortList(head2); // 递归地对右半部分链表排序
        return mergeTwoLists(head, head2); // 将两个有序链表合并为一个
    }
};

思路详解

这段代码实现了 归并排序（Merge Sort）在链表上的应用，通过递归的方式将链表分割成两个部分，然后排序并合并。

核心思路

1. 拆分链表：

使用快慢指针（middleNode 函数）找到链表的中间节点，将链表拆分为两部分。

2. 递归排序：

对拆分后的两部分链表分别递归调用 sortList，直到链表被拆分为单个节点（此时链表自然是有序的）。

3. 合并链表：

使用双指针（mergeTwoLists 函数）将两个有序链表合并为一个有序链表。

代码分析

1. middleNode 函数（找到中间节点并断开链表）

ListNode* middleNode(ListNode* head) {

    ListNode* slow = head;

    ListNode* fast = head;

    while (fast->next && fast->next->next) {

        slow = slow->next;

        fast = fast->next->next;

    }

    ListNode* mid = slow->next; // 中间节点

    slow->next = nullptr;       // 断开链表

    return mid;

}

• 功能：找到链表的中间节点并断开链表。

• 原理：使用快慢指针：

• 快指针 fast 每次移动两步；

• 慢指针 slow 每次移动一步；

• 当 fast 到达链表末尾时，slow 指向链表的中间节点。

• 返回值：mid 是中间节点的指针，用于分割链表。

2. mergeTwoLists 函数（合并两个有序链表）

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

    ListNode dummy; // 哨兵节点，简化合并过程

    ListNode* cur = &dummy;

    while (list1 && list2) {

        if (list1->val < list2->val) {

            cur->next = list1;

            list1 = list1->next;

        } else {

            cur->next = list2;

            list2 = list2->next;

        }

        cur = cur->next;

    }

    cur->next = list1 ? list1 : list2; // 拼接剩余链表

    return dummy.next; // 返回合并后的链表

}

• 功能：将两个有序链表合并为一个有序链表。

• 原理：使用双指针逐个比较两个链表的节点值，将较小值的节点连接到新链表上，直到其中一个链表为空。

• 返回值：合并后的链表头指针。

3. sortList 函数（链表归并排序的入口）

ListNode* sortList(ListNode* head) {

    if (head == nullptr || head->next == nullptr) {

        return head; // 链表为空或只有一个节点，无需排序

    }

    ListNode* head2 = middleNode(head); // 分割链表

    head = sortList(head);              // 递归排序左部分

    head2 = sortList(head2);            // 递归排序右部分

    return mergeTwoLists(head, head2);  // 合并两个有序链表

}

• 功能：实现链表的归并排序。

• 分割链表：

• 调用 middleNode 函数找到链表的中间节点，并将链表分为两部分。

• 比如 [4,2,1,3] 分为 [4,2] 和 [1,3]。

• 递归排序：

• 递归地对两部分链表分别调用 sortList 进行排序。

• 递归终止条件是链表为空或只有一个节点。

• 合并链表：

• 调用 mergeTwoLists 函数将两个有序链表合并为一个。

算法过程

递归是一种通过函数调用自身来解决问题的方式，它通常分为两部分：终止条件和递推关系。每一层递归会在满足特定条件后返回结果，并将结果传递给上一层递归调用。下面以链表排序 sortList 函数为例，详细说明递归的每一层操作。

每一层递归如何工作

以链表 [4, 2, 1, 3] 为例，说明每一层递归的处理过程。

第 1 层递归

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

• 中间节点：middleNode 找到 mid = 1，链表被分为两部分：

• head = [4, 2]

• head2 = [1, 3]

• 递归调用：

• 对 [4, 2] 和 [1, 3] 分别调用 sortList。

第 2 层递归

• 左侧递归：

• 输入：head = [4, 2]

• 中间节点：mid = 2，链表分为：

• head = [4]

• head2 = [2]

• 递归调用：

• 对 [4] 和 [2] 调用 sortList。

• 合并结果：

• mergeTwoLists([4], [2]) 返回 [2, 4]。

• 右侧递归：

• 输入：head = [1, 3]

• 中间节点：mid = 3，链表分为：

• head = [1]

• head2 = [3]

• 递归调用：

• 对 [1] 和 [3] 调用 sortList。

• 合并结果：

• mergeTwoLists([1], [3]) 返回 [1, 3]。

第 3 层递归

• 输入：

• [4] 和 [2]：直接返回，因为链表只有一个节点或为空。

• [1] 和 [3]：同样直接返回。

回溯过程

• 第 2 层返回：

• 左侧 [4, 2] 合并为 [2, 4]。

• 右侧 [1, 3] 合并为 [1, 3]。

• 第 1 层合并：

• mergeTwoLists([2, 4], [1, 3]) 返回 [1, 2, 3, 4]。

总结

• 每层递归处理的是将链表分为两部分，并对每部分递归调用 sortList。

• 在回溯时，通过 mergeTwoLists 合并两个有序链表。

• 递归终止条件：链表为空或只有一个节点时，直接返回。

• 递归的深度：链表长度为 ，递归深度为 。

原文地址：https://blog.csdn.net/qq_51956059/article/details/145183242

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！