设有两个链式线性表La,L吧,表中数据递增排序,现将两张链式线性表合并,合并后,线性表也递增有序在Dev-C++中写出代码
时间: 2024-09-18 18:01:57 浏览: 68
在Dev-C++中合并两个升序排列的链表,你可以创建一个新的链表,并按照顺序遍历两个输入链表,将较小的节点添加到新链表中。以下是简单的伪代码和示例Dev-C++代码:
**伪代码步骤:**
1. 创建一个新的头结点
2. 初始化两个指针,分别指向两个链表的头部
3. 比较当前节点值,将较小的节点添加到新链表并移动指针
4. 当其中一个链表遍历完,将另一个链表剩余部分连接到新链表
**Dev-C++代码(C++实现):**
```cpp
#include <iostream>
using namespace std;
// 定义链表节点结构
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 合并两个升序链表
ListNode* mergeSortedLists(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
ListNode* result = new ListNode(0); // 新链表头部
ListNode* tail = result; // 尾部指针
while (l1 && l2) { // 遍历直到有一个链表结束
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// 如果其中一个链表还有剩余元素,将其添加到结果链表
if (l1) tail->next = l1;
else tail->next = l2;
return result->next;
}
int main() {
// 这里假设你已经定义了链表的节点并填充了数据
// 示例:ListNode* la = ...; ListNode* lb = ...;
ListNode* mergedList = mergeSortedLists(la, lb);
// 打印合并后的链表
while (mergedList) {
cout << mergedList->val << " ";
mergedList = mergedList->next;
}
cout << endl;
return 0;
}
```
阅读全文