写C++代码,使用简单的单向链表实现。描述:将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。输入(读取文件: List.in) 总共4行内容,第一行n,代表第一个升序链表的元素个数: 第二行是组成第一个链表的n个正整教(正整教小于等于50): 第三行m,代表第二个升序链表的元素个数: 第四行是组成第二个链表的m个正整数 输出(写入文件: List.out) 输出组合之后的链表元素
时间: 2023-06-28 12:14:46 浏览: 84
使用C++实现单链表的基本操作:1、创建单链表2、遍历单链表3、单链表插入4、删除单链表5、判断是否为空6、单链表的
5星 · 资源好评率100%
以下是使用简单的单向链表实现的解法:
```c++
#include <iostream>
#include <fstream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(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() {
ifstream fin("List.in");
int n, m;
fin >> n;
ListNode* l1 = NULL;
ListNode* cur = l1;
for (int i = 0; i < n; i++) {
int x;
fin >> x;
if (l1 == NULL) {
l1 = new ListNode(x);
cur = l1;
} else {
cur->next = new ListNode(x);
cur = cur->next;
}
}
fin >> m;
ListNode* l2 = NULL;
cur = l2;
for (int i = 0; i < m; i++) {
int x;
fin >> x;
if (l2 == NULL) {
l2 = new ListNode(x);
cur = l2;
} else {
cur->next = new ListNode(x);
cur = cur->next;
}
}
fin.close();
ListNode* res = mergeTwoLists(l1, l2);
ofstream fout("List.out");
while (res) {
fout << res->val << " ";
res = res->next;
}
fout.close();
return 0;
}
```
该代码中同样定义了一个链表结构体ListNode,包含一个整数值和一个指向下一个节点的指针。在主函数中,首先从文件中读取两个升序链表的元素,分别构建两个链表l1和l2。然后调用mergeTwoLists函数将两个链表合并成一个链表,返回合并后的链表头节点指针res,最后将结果写入文件。与之前的解法不同的是,这里使用简单的单向链表实现,没有使用STL容器。
阅读全文