编写程序实现将两个带头结点的单链表,合并为一个带头结点的单链表,使用C++编写一个简单代码
时间: 2024-05-07 14:20:18 浏览: 102
下面是一个简单的C++代码实现:
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(0);
ListNode *cur = dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy->next;
}
int main() {
// 构造两个链表
ListNode *l1 = new ListNode(1);
l1->next = new ListNode(3);
l1->next->next = new ListNode(5);
ListNode *l2 = new ListNode(2);
l2->next = new ListNode(4);
l2->next->next = new ListNode(6);
// 合并两个链表
ListNode *merged = mergeTwoLists(l1, l2);
// 输出合并后的链表
while (merged) {
cout << merged->val << " ";
merged = merged->next;
}
cout << endl;
return 0;
}
```
该程序首先定义了一个结构体`ListNode`表示链表中的一个节点,并且定义了一个函数`mergeTwoLists`用于将两个带头结点的单链表合并为一个带头结点的单链表。程序中的主要逻辑是利用两个指针`l1`和`l2`分别指向两个链表的头节点,然后不断比较`l1`和`l2`节点的值,将较小的节点插入到新链表中,直到其中一个链表为空。最后,将剩余的链表直接接到新链表的末尾即可。注意,程序中还定义了一个虚拟头节点`dummy`,这是为了方便处理链表的边界情况。
阅读全文