用c++编译程序将两个升序链list1 list2表合并为一个新的升序链表并返回,新链表是通过拼接给定的两个链表的所有节点组成的
时间: 2024-09-15 09:02:44 浏览: 39
在C++中,合并两个已排序的链表可以使用迭代的方法,通过比较两个链表的头节点,并创建一个新的链表来存储所有节点。具体步骤如下:
1. 创建一个新的链表,用一个哑节点(dummy node)作为新链表的头部,以便简化边界条件。
2. 使用两个指针,分别指向两个输入链表的头部。
3. 比较这两个指针所指向的节点的值,将较小值的节点接到新链表的尾部,并将该指针向后移动一个节点。
4. 重复步骤3,直到一个链表遍历完成。
5. 如果其中一个链表还有剩余节点,将它们全部接到新链表的尾部。
6. 最后返回新链表的头部(哑节点的下一个节点)。
下面是一个简单的C++函数实现:
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0); // 创建哑节点
ListNode *tail = &dummy; // tail用于构建新链表
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指针
}
// 如果其中一个链表为空,则直接将另一个链表接到尾部
tail->next = l1 ? l1 : l2;
return dummy.next; // 返回哑节点的下一个节点
}
```
注意:这里假设链表的节点结构体为`ListNode`,并且已经定义了相应的构造函数。
阅读全文