用C++将两个有序的链表合并成一个有序的链表
时间: 2024-10-09 12:16:20 浏览: 23
在C++中,合并两个有序链表可以使用迭代或递归的方式实现。这里我们提供一种简单的迭代方法:
首先,你需要定义一个链表节点的结构体,例如:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
```
接下来,我们可以创建一个函数`mergeTwoLists(ListNode** headA, ListNode** headB)`来合并这两个链表:
```cpp
ListNode* mergeTwoLists(ListNode* headA, ListNode* headB) {
if (!headA) return headB; // 如果headA为空,直接返回头B
if (!headB) return headA; // 如果headB为空,直接返回头A
ListNode dummy(0); // 创建虚拟头结点,避免处理边界情况
ListNode* tail = &dummy; // 尾指针指向虚拟头
while (headA && headB) { // 当两个链表都不为空
if (headA->val < headB->val) {
tail->next = headA;
headA = headA->next;
} else {
tail->next = headB;
headB = headB->next;
}
tail = tail->next; // 更新尾部指针
}
// 如果其中一个链表已经遍历完,就将其剩余部分添加到结果链表末尾
if (headA) tail->next = headA;
if (headB) tail->next = headB;
return dummy.next; // 返回合并后的实际链表头节点
}
```