c语言,将两个有序单循环链表La和Lb合并为一个新的有序链表。并提供代码
时间: 2024-05-11 14:17:11 浏览: 190
c++ 如何合并两个有序链表
以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} Node, *LinkList;
// 创建单循环链表
LinkList createLinkList(int arr[], int n) {
LinkList L = NULL, p = NULL;
for (int i = 0; i < n; i++) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = arr[i];
if (L == NULL) {
L = node;
p = L;
L->next = p;
} else {
p->next = node;
p = node;
p->next = L;
}
}
return L;
}
// 合并两个有序单循环链表
LinkList mergeLinkList(LinkList La, LinkList Lb) {
LinkList Lc = La;
Node *pa = La->next, *pb = Lb->next;
// 将pb链表中的节点插入到La链表中
while (pa != La && pb != Lb) {
if (pa->data <= pb->data) {
Lc->next = pa;
Lc = pa;
pa = pa->next;
} else {
Lc->next = pb;
Lc = pb;
pb = pb->next;
}
}
// 如果La链表没有遍历完,将La链表剩余的节点插入到Lc链表中
if (pa != La) {
Lc->next = pa;
}
// 如果Lb链表没有遍历完,将Lb链表剩余的节点插入到Lc链表中
if (pb != Lb) {
Lc->next = pb;
}
// 将Lc链表的最后一个节点指向La链表的第一个节点,形成单循环链表
Lc->next = La;
return La;
}
// 打印单循环链表
void printLinkList(LinkList L) {
Node *p = L;
do {
printf("%d ", p->data);
p = p->next;
} while (p != L);
printf("\n");
}
int main() {
int arr1[] = {1, 3, 5, 7};
int arr2[] = {2, 4, 6, 8};
int n1 = sizeof(arr1) / sizeof(int);
int n2 = sizeof(arr2) / sizeof(int);
LinkList La = createLinkList(arr1, n1);
LinkList Lb = createLinkList(arr2, n2);
LinkList Lc = mergeLinkList(La, Lb);
printLinkList(Lc);
return 0;
}
```
代码实现的思路是:
1. 首先,创建两个有序单循环链表La和Lb。
2. 定义指针pa和pb分别指向La和Lb链表的第一个节点。
3. 定义指针Lc指向La链表的第一个节点,用来记录合并后的新链表。
4. 将pb链表中的节点插入到La链表中,使La链表保持有序性。
5. 如果La链表没有遍历完,将La链表剩余的节点插入到Lc链表中。
6. 如果Lb链表没有遍历完,将Lb链表剩余的节点插入到Lc链表中。
7. 最后,将Lc链表的最后一个节点指向La链表的第一个节点,形成单循环链表。
8. 打印合并后的新链表Lc。
以上就是将两个有序单循环链表合并为一个新的有序链表的C语言代码实现。
阅读全文