c++中如何合并两个链表_c++链表合并方法-C++-PHP中文网

c++中如何合并两个链表_c++链表合并方法

尼克

发布： 2025-09-29 09:48:02

原创

614人浏览过

合并两个链表有两种常见方式：一是拼接，将一个链表接在另一个末尾，需遍历找到尾节点；二是归并有序链表，使用双指针比较节点值，时间复杂度O(m+n)，空间复杂度O(1)。

c++中如何合并两个链表_c++链表合并方法

在C++中合并两个链表，通常指的是将两个已存在的单向链表连接成一个链表。根据需求不同，合并可以是简单地将一个链表接到另一个链表的末尾（拼接），也可以是将两个有序链表合并为一个新的有序链表（如归并排序中的合并操作）。下面介绍两种常见情况的实现方法。

1. 拼接两个链表（尾接头）

如果目标是将链表B接到链表A的末尾，只需要找到链表A的最后一个节点，将其next指针指向链表B的头节点即可。

若链表A为空，直接返回B的头节点。
若链表B为空，返回A的头节点。
遍历链表A到最后一个节点，将其next指向B的头节点。

示例代码：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
<p>ListNode<em> mergeLists(ListNode</em> headA, ListNode* headB) {
if (!headA) return headB;
if (!headB) return headA;</p><pre class='brush:php;toolbar:false;'>ListNode* current = headA;
while (current->next) {
    current = current->next;
}
current->next = headB;
return headA;

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

2. 合并两个有序链表（归并方式）

当两个链表各自按升序排列时，可以使用双指针技术合并成一个有序链表，类似归并排序的合并过程。

Cowriter

AI 作家，帮助加速和激发你的创意写作

107

查看详情

使用一个虚拟头节点（dummy）简化插入操作。
用两个指针分别指向两个链表的头部，比较节点值，将较小的节点接入结果链表。
最后将剩余非空链表直接接在结果链表后。

示例代码：

ListNode* mergeTwoSortedLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
<pre class='brush:php;toolbar:false;'>while (l1 && l2) {
    if (l1->val <= l2->val) {
        tail->next = l1;
        l1 = l1->next;
    } else {
        tail->next = l2;
        l2 = l2->next;
    }
    tail = tail->next;
}

tail->next = l1 ? l1 : l2;
return dummy.next;

登录后复制

}

立即学习“C++免费学习笔记（深入）”；

这种方法时间复杂度为O(m+n)，空间复杂度为O(1)，效率高且适用于有序链表的合并场景。

基本上就这些。根据实际需求选择拼接或归并方式即可。

以上就是c++++中如何合并两个链表_c++链表合并方法的详细内容，更多请关注php中文网其它相关文章！