用C语言表示:知单链表LA=(a1,a2,…,am)和LB=(b1,b2,…,bn),编写程序按以下规则将它们合并成一个单链表LC,要求新表 LC利用原表的存储空间。 LC=(a1,b1,…,am,bm,bm+1,…,bn),m<=n
时间: 2024-05-03 13:18:05 浏览: 77
C语言单链表的实现
以下是用C语言实现将两个单链表合并为一个单链表的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} ListNode;
// 合并两个单链表
ListNode* mergeLists(ListNode* la, ListNode* lb) {
ListNode *p, *q, *r;
p = la->next; // 指向链表LA的第一个节点
q = lb->next; // 指向链表LB的第一个节点
r = la; // 指向链表LA的头节点
while (p != NULL && q != NULL) {
if (p->data <= q->data) {
r->next = p;
r = p;
p = p->next;
} else {
r->next = q;
r = q;
q = q->next;
}
}
// 将剩下的节点加入到新链表中
if (p != NULL) {
r->next = p;
} else {
r->next = q;
}
return la;
}
int main() {
ListNode *la, *lb, *lc;
int m, n, i, x;
// 创建链表LA
scanf("%d", &m);
la = (ListNode*)malloc(sizeof(ListNode));
la->next = NULL;
for (i = 1; i <= m; i++) {
scanf("%d", &x);
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->data = x;
node->next = la->next;
la->next = node;
}
// 创建链表LB
scanf("%d", &n);
lb = (ListNode*)malloc(sizeof(ListNode));
lb->next = NULL;
for (i = 1; i <= n; i++) {
scanf("%d", &x);
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->data = x;
node->next = lb->next;
lb->next = node;
}
// 合并链表LA和LB
lc = mergeLists(la, lb);
// 输出链表LC
ListNode* p = lc->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
return 0;
}
```
上述代码中,我们先定义了一个单链表的结构体 `ListNode`,然后实现了一个函数 `mergeLists` 来合并两个单链表。具体来说,我们使用三个指针 `p`、`q`、`r` 分别指向链表 LA、LB 和 LC 的当前节点,然后依次比较 `p` 和 `q` 指向的节点,将较小的节点加入到 LC 中,并将当前节点向后移动一位。最后,将剩下的节点加入到 LC 中即可。
在 `main` 函数中,我们先创建链表 LA 和 LB,然后调用 `mergeLists` 函数将它们合并为链表 LC,最后输出链表 LC 中的所有节点。
阅读全文