用c语言编写一个代码,设ha 和hb 分别是两个带头结点的递增有序单链表。设计一个算法,将这两个有序链表的所有数据结点合并成一个递增有序的单链表hc,并用相关数据进行测试。
时间: 2024-09-25 11:20:22 浏览: 46
为了合并两个递增有序的单链表 ha 和 hb,并创建一个新的有序链表 hc,你可以使用迭代的方式遍历每个列表并比较节点值。以下是简单的 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建新节点
Node* newNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 比较并合并两个有序链表
Node* mergeSortedLists(Node* ha, Node* hb) {
// 初始化头节点
Node* head = NULL;
if (ha == NULL) {
return hb;
}
else if (hb == NULL) {
return ha;
}
// 初始条件:ha 的当前元素小于 hb 的当前元素
if (ha->data <= hb->data) {
head = ha;
ha = ha->next; // 移动 ha 到下一个元素
} else {
head = hb;
hb = hb->next; // 移动 hb 到下一个元素
}
// 迭代合并两个链表
while (ha && hb) {
if (ha->data <= hb->data) {
head->next = ha;
ha = ha->next;
} else {
head->next = hb;
hb = hb->next;
}
head = head->next;
}
// 将剩余部分添加到结果链表
if (ha) {
head->next = ha;
} else {
head->next = hb;
}
return head;
}
// 测试函数
void printList(Node* list) {
while (list != NULL) {
printf("%d -> ", list->data);
list = list->next;
}
printf("NULL\n");
}
int main() {
// 创建两个示例链表
Node* ha = newNode(1);
ha->next = newNode(3);
ha->next->next = newNode(5);
Node* hb = newNode(2);
hb->next = newNode(4);
hb->next->next = newNode(6);
// 合并链表
Node* hc = mergeSortedLists(ha, hb);
// 打印合并后的链表
printf("Merged list: ");
printList(hc);
return 0;
}
```
在这个代码中,`mergeSortedLists` 函数接收两个链表的头节点作为输入,然后通过比较它们的数据值逐个合并它们,生成一个新的递增有序链表。
阅读全文