力扣148题：合并两个有序链表的归并排序解法（递归分治优化详解）

一、题目解读

力扣148题要求合并两个有序链表，返回一个有序链表。题目核心在于处理链表节点指针的遍历与合并逻辑，需确保合并后的链表保持升序。输入为两个已排序的链表头节点，输出为合并后的链表头节点。例如，输入链表1：1→3→5，链表2：2→4→6，则输出应为1→2→3→4→5→6。

二、解题思路

采用归并排序思想，通过递归分治策略将问题拆解：

1. 分治阶段：使用快慢指针定位链表中间节点，递归拆分链表为左右两部分，直至子链表长度为1或0（天然有序）。

2. 合并阶段：对两个有序子链表进行迭代合并，比较节点值后依次连接，最终形成完整有序链表。

该解法巧妙利用递归实现链表的“自底向上”排序，避免了额外空间的开辟（仅递归栈消耗）。

三、解题步骤

1. 入口函数sortList递归拆解：

    判断链表长度是否≤1，若成立则直接返回（基递归条件）。

    快慢指针找到链表中间节点，切断后半段（pre->next = nullptr），递归调用sortList分别对左右子链表排序。

2. 合并函数merge迭代整合：

    创建虚拟头节点head，通过tmp指针遍历合并过程。

    比较a、b节点值，将较小节点连接至tmp->next，并移动对应指针。

    处理剩余单链表尾段，最终返回head->next（去除虚拟头）。

四、代码与注释

class Solution {
public:
    ListNode* merge(ListNode* a, ListNode* b) {
        // 创建虚拟头节点并遍历合并
        ListNode* head = new ListNode;
        ListNode* tmp = head;
        while (a || b) {
            if (a) { // a存在时比较
                if (b) { // a、b均存在，取较小值
                    if (a->val < b->val) {
                        tmp->next = a;  
                        a = a->next;
                    } else { 
                        tmp->next = b;
                        b = b->next;
                    }
                } else { // a存在且b为空，直接连接a剩余部分
                    tmp->next = a;  
                    a = a->next;
                } 
            } else { // a为空，直接连接b剩余部分
                tmp->next = b;
                b = b->next;
            }
            // 移动tmp至当前合并节点末尾
            tmp = tmp->next;
            // 手动置空防止野指针
            tmp->next = nullptr;
        }
        return head->next;
    }
    ListNode* sortList(ListNode* head) {
        // 递归终止条件
        if (!head ||!head->next) return head;
        // 快慢指针拆分链表
        ListNode* fast = head, *slow = head, *pre = nullptr;
        while (fast) {
            pre = slow; // 记录slow前驱（用于切断链表）
            slow = slow->next;
            fast = fast->next;
            // 偶数长度时fast多走一步
            if (fast) fast = fast->next;
        }
        // 切断链表后半段
        pre->next = nullptr;
        // 递归排序左右子链表并合并
        return merge(head, slow);
    }
};

五、总结

本解法通过递归分治将链表排序问题转化为子链表的合并，兼具优雅性与高效性（时间复杂度O(nlogn)，空间复杂度O(logn)）。需注意：

    快慢指针分割链表时需处理偶数长度的特殊逻辑；

    合并阶段采用虚拟头节点简化边界处理；

    递归深度与链表长度相关，适用于中小规模数据场景。

该算法为链表排序的经典范式，对理解分治思想具有重要价值。