用C语言表示:知单链表LA=(a1,a2,…,am)和LB=(b1,b2,…,bn),编写程序按以下规则将它们合并成一个单链表LC,要求新表 LC利用原表的存储空间。 LC=(a1,b1,…,am,bm,bm+1,…,bn),m<=n
时间: 2024-05-03 22:18:11 浏览: 117
c语言:创建单链表的头插法代码
以下是用C语言实现将两个单链表合并成一个的程序:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义单链表节点结构体
struct ListNode {
int val;
struct ListNode *next;
};
// 定义函数将两个单链表合并成一个
struct ListNode* mergeLists(struct ListNode* LA, struct ListNode* LB) {
struct ListNode *p = LA->next; // LA的第一个节点
struct ListNode *q = LB->next; // LB的第一个节点
struct ListNode *pre = LA; // pre表示LC的前驱节点
while (p && q) { // p和q都不为空时
if (p->val <= q->val) {
pre->next = p;
p = p->next;
} else {
pre->next = q;
q = q->next;
}
pre = pre->next; // LC的前驱节点指向当前节点
}
pre->next = p ? p : q; // 将未遍历完的链表连接到LC末尾
free(LB); // 释放LB的头节点
return LA;
}
int main() {
// 初始化LA和LB
struct ListNode *LA = (struct ListNode*)malloc(sizeof(struct ListNode));
LA->next = NULL;
struct ListNode *LB = (struct ListNode*)malloc(sizeof(struct ListNode));
LB->next = NULL;
// 生成LA和LB的节点
struct ListNode *p = LA;
for (int i = 1; i <= 5; i++) {
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = i;
node->next = NULL;
p->next = node;
p = node;
}
p = LB;
for (int i = 6; i <= 10; i++) {
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = i;
node->next = NULL;
p->next = node;
p = node;
}
// 将LA和LB合并成LC
struct ListNode *LC = mergeLists(LA, LB);
// 输出LC的值
p = LC->next;
while (p) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");
// 释放LA、LB和LC的所有节点
p = LA;
while (p) {
struct ListNode *node = p;
p = p->next;
free(node);
}
p = LB;
while (p) {
struct ListNode *node = p;
p = p->next;
free(node);
}
p = LC;
while (p) {
struct ListNode *node = p;
p = p->next;
free(node);
}
return 0;
}
```
程序的核心就是一个`mergeLists`函数,它将两个单链表合并成一个并返回合并后的链表的头节点指针。在函数中,我们先定义三个指针`p`、`q`和`pre`,分别指向LA的第一个节点、LB的第一个节点和LC的前驱节点。然后从链表的头开始,比较p和q节点的值,将较小的节点连接到LC的末尾。最后将未遍历完的链表连接到LC的末尾即可。最后别忘了释放LB的头节点和所有的节点。
阅读全文