两个递增有序链表合并成一个递增有序链表cpp
时间: 2024-10-15 22:20:17 浏览: 8
在C++中,合并两个递增有序链表可以使用迭代或递归的方式来实现。这里我将提供一种迭代的方法,因为它更直观且效率更高。假设我们有两个头结点为`head1`和`head2`的递增排序链表。
```cpp
// 定义链表节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* mergeTwoLists(ListNode* head1, ListNode* head2) {
// 创建一个新的空链表作为结果
ListNode* dummy = new ListNode(0);
ListNode* current = dummy; // 当前指针
// 当其中一个链表为空时,直接返回另一个链表
while (head1 && head2) {
if (head1->val < head2->val) { // 如果第一个值小,添加第一个并移动指针
current->next = head1;
head1 = head1->next;
} else { // 否则,添加第二个值
current->next = head2;
head2 = head2->next;
}
current = current->next; // 移动到下一个位置
}
// 将剩余未处理的部分添加到结果链表中
if (head1) {
current->next = head1;
} else {
current->next = head2;
}
return dummy->next; // 返回新合并后的链表头节点
}
```
在这个函数中,我们首先创建一个虚拟头节点`dummy`用于简化边界情况的处理。然后通过比较两个链表当前节点的值,不断选择较小的那个节点添加到结果链表中,并更新指针。最后返回合并后的链表头节点。
阅读全文