循环链表的合并c++
时间: 2024-09-29 13:03:52 浏览: 29
数据结构C++版的双循环链表
循环链表的合并是指将两个已排序的循环链表合并成一个新的有序循环链表。在C++中,我们可以采用类似于归并排序的思想来进行操作,首先遍历两个链表,取出最小元素添加到新链表,并更新指向较小元素的指针,直到其中一个链表遍历完,然后将另一个链表剩余的部分接到新链表的末尾。
这里是一个简单的C++示例:
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0); // 创建虚拟头节点
ListNode* tail = &dummy; // 指向虚拟头节点
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
}
// 如果有一个链表还剩下未添加,直接接上
if (l1) {
tail->next = l1;
} else {
tail->next = l2;
}
return dummy.next; // 返回新链表的头节点
}
```
阅读全文