C++面试(10)---合并两个排序的链表

• 操作系统：ubuntu22.04
• IDE:Visual Studio Code
• 编程语言：C++11

题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然递增有序。
你可以选择不修改原链表，也可以就地合并（视题目要求）。

示例：

输入：
链表1: 1 -> 2 -> 4
链表2: 1 -> 3 -> 4

输出：
合并后链表: 1 -> 1 -> 2 -> 3 -> 4 -> 4

解法思路：双指针归并法

这个题目是链表操作的经典问题，和“归并排序”中合并两个有序数组非常类似。
思路总结：

• 使用两个指针 l1 和 l2 分别遍历两个链表；
• 创建一个虚拟头节点 dummy，便于统一处理；
• 创建一个指针 cur 跟随构建结果链表；
• 每次比较 l1->val 和 l2->val，把较小的节点接到 cur->next，然后移动相应指针；
• 当其中一个链表为空时，直接将另一个链表剩余部分接上即可；
• 最后返回 dummy.next 就是合并后的链表头节点。

C++ 实现代码

// 定义链表结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode( int x ) : val( x ), next( nullptr ) {}
};

ListNode* mergeTwoLists( ListNode* l1, ListNode* l2 )
{
    // 创建一个虚拟头节点，方便统一处理
    ListNode dummy( 0 );
    ListNode* cur = &dummy;  // 当前指针，用于构建新链表

    // 同时遍历两个链表，直到其中一个为空
    while ( l1 != nullptr && l2 != nullptr )
    {
        if ( l1->val < l2->val )
        {
            cur->next = l1;        // 把 l1 接到结果链表末尾
            l1        = l1->next;  // 移动 l1 指针
        }
        else
        {
            cur->next = l2;        // 把 l2 接到结果链表末尾
            l2        = l2->next;  // 移动 l2 指针
        }
        cur = cur->next;  // 结果链表指针后移一位
    }

    // 如果还有剩余节点，直接接到结果链表后面
    cur->next = ( l1 != nullptr ) ? l1 : l2;

    // 返回合并后的链表头节点（即 dummy 的下一个节点）
    return dummy.next;
}

int main()
{
    ListNode* node1               = new ListNode( 1 );
    node1->next                   = new ListNode( 2 );
    node1->next->next             = new ListNode( 3 );
    node1->next->next->next       = new ListNode( 4 );
    node1->next->next->next->next = new ListNode( 5 );

    ListNode* node2               = new ListNode( 1 );
    node2->next                   = new ListNode( 2 );
    node2->next->next             = new ListNode( 3 );
    node2->next->next->next       = new ListNode( 4 );
    node2->next->next->next->next = new ListNode( 5 );

    ListNode* res = mergeTwoLists( node1, node2 );
    while ( res != nullptr )
    {

        std::cout << res->val << std::endl;
        res = res->next;
    }
}

输出：

1
1
2
2
3
3
4
4
5
5