当前位置：首页 > ai >正文

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

ai 2025/6/18 20:53:30

操作系统：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;}
}