设计算法,将两个带头节点的递增有序的单链表A和B合并到一个单链表C中,单链表C仍然递增有序。C语言代码
时间: 2023-03-24 15:01:44 浏览: 65
以下是将两个带头结点的有序单链表A和B合并到一个单链表C中,并保持C有序的C语言代码:
```
#include<stdio.h>
#include<stdlib.h>
struct Node {
int data;
struct Node* next;
};
// 创建一个带头结点的单链表
struct Node* createLinkedList() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->next = NULL;
return head;
}
// 将值为value的结点插入到带头结点的单链表中
void insertNode(struct Node* head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
struct Node* cur = head;
while (cur->next != NULL && cur->next->data < value) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
}
// 合并两个带头结点的有序单链表A和B到一个带头结点的有序单链表C中
struct Node* mergeLinkedList(struct Node* A, struct Node* B) {
struct Node* C = createLinkedList();
struct Node* curA = A->next;
struct Node* curB = B->next;
while (curA != NULL && curB != NULL) {
if (curA->data < curB->data) {
insertNode(C, curA->data);
curA = curA->next;
}
else {
insertNode(C, curB->data);
curB = curB->next;
}
}
while (curA != NULL) {
insertNode(C, curA->data);
curA = curA->next;
}
while (curB != NULL) {
insertNode(C, curB->data);
curB = curB->next;
}
return C;
}
// 输出带头结点的单链表中的所有结点值
void printLinkedList(struct Node* head) {
struct Node* cur = head->next;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
// 测试
int main() {
struct Node* A = createLinkedList();
insertNode(A, 1);
insertNode(A, 3);
insertNode(A, 5);
printf("A: ");
printLinkedList(A);
struct Node* B = createLinkedList();
insertNode(B, 2);
insertNode(B, 4);
insertNode(B, 6);
printf("B: ");
printLinkedList(B);
struct Node* C = mergeLinkedList(A, B);
printf("C: ");
printLinkedList(C);
return 0;
}
```
在这个程序中,我们首先创建了一个带头结点的单链表,然后通过 `insertNode` 函数将数据插入到单链表中。在 `mergeLinkedList` 函数中,我们使用了两个指针 `curA` 和 `curB` 分别指向链表 A 和 B 的第一个数据结点,然后依次比较这两个指针指向的结点的值,将较小的结点插入到链表 C