用c语言的代码实现单链表的合并的代码
时间: 2023-06-05 13:05:08 浏览: 68
请参考以下代码:
struct Node {
int val;
struct Node* next;
};
struct Node* mergeLinkedList(struct Node* l1, struct Node* l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
if (l1->val <= l2->val) {
l1->next = mergeLinkedList(l1->next, l2);
return l1;
} else {
l2->next = mergeLinkedList(l1, l2->next);
return l2;
}
}
相关问题
用c语言实现两个单链表的合并
以下是用C语言实现两个单链表合并的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* mergeLists(struct Node* head1, struct Node* head2) {
if (head1 == NULL) {
return head2;
}
if (head2 == NULL) {
return head1;
}
struct Node* mergedHead = NULL;
if (head1->data < head2->data) {
mergedHead = head1;
mergedHead->next = mergeLists(head1->next, head2);
} else {
mergedHead = head2;
mergedHead->next = mergeLists(head1, head2->next);
}
return mergedHead;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
int main() {
struct Node* head1 = NULL;
struct Node* head2 = NULL;
// add nodes to list 1
head1 = (struct Node*) malloc(sizeof(struct Node));
head1->data = 1;
head1->next = (struct Node*) malloc(sizeof(struct Node));
head1->next->data = 2;
head1->next->next = (struct Node*) malloc(sizeof(struct Node));
head1->next->next->data = 4;
head1->next->next->next = NULL;
// add nodes to list 2
head2 = (struct Node*) malloc(sizeof(struct Node));
head2->data = 1;
head2->next = (struct Node*) malloc(sizeof(struct Node));
head2->next->data = 3;
head2->next->next = (struct Node*) malloc(sizeof(struct Node));
head2->next->next->data = 4;
head2->next->next->next = NULL;
printf("List 1: ");
printList(head1);
printf("List 2: ");
printList(head2);
struct Node* mergedHead = mergeLists(head1, head2);
printf("Merged List: ");
printList(mergedHead);
return 0;
}
```
在上面的代码中,我们首先定义了一个名为“Node”的结构体,用于表示链表中的每个节点。然后,我们定义了一个名为“mergeLists”的函数,该函数接受两个链表的头节点作为参数,并返回一个指向合并后链表的头节点的指针。
在“mergeLists”函数中,我们首先检查两个链表中是否有一个为空,如果是,则返回另一个链表。否则,我们比较两个链表的第一个节点的数据,将较小的节点作为合并后链表的头节点。然后,我们递归调用“mergeLists”函数,将未合并的链表和较小节点的下一个节点作为参数,并将返回的链表连接到较小节点的下一个节点上。
最后,我们定义了一个名为“printList”的函数,用于打印链表中的所有节点。在“main”函数中,我们首先创建两个链表,并将节点添加到它们中。然后,我们打印两个链表,并调用“mergeLists”函数来合并它们。最后,我们打印合并后的链表。
C语言单链表有序表合并的代码
以下是C语言单链表有序表合并的代码:
```
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node* next;
}Node;
Node* CreateListNode(int data){
Node* pNew = (Node*)malloc(sizeof(Node));
if (pNew == NULL){
printf("Error: out of memory!\n");
exit(1);
}
pNew->data = data;
pNew->next = NULL;
return pNew;
}
void PrintList(Node* head){
Node* pNode = head;
if (pNode == NULL){
printf("Error: empty list!\n");
return;
}
while (pNode != NULL){
printf("%d ", pNode->data);
pNode = pNode->next;
}
printf("\n");
}
Node* MergeSortedList(Node* head1, Node* head2){
if (head1 == NULL)
return head2;
else if (head2 == NULL)
return head1;
Node* pMerge = NULL;
if (head1->data < head2->data){
pMerge = head1;
pMerge->next = MergeSortedList(head1->next, head2);
}
else{
pMerge = head2;
pMerge->next = MergeSortedList(head1, head2->next);
}
return pMerge;
}
int main(){
int data1[] = {1, 3, 4, 6, 8};
int data2[] = {-2, 0, 2, 3, 5, 7, 9};
int len1 = sizeof(data1)/sizeof(data1[0]);
int len2 = sizeof(data2)/sizeof(data2[0]);
Node* head1 = CreateListNode(data1[0]);
Node* head2 = CreateListNode(data2[0]);
Node* pNode = head1;
for (int i=1; i<len1; ++i){
pNode->next = CreateListNode(data1[i]);
pNode = pNode->next;
}
pNode = head2;
for (int i=1; i<len2; ++i){
pNode->next = CreateListNode(data2[i]);
pNode = pNode->next;
}
printf("List1: ");
PrintList(head1);
printf("List2: ");
PrintList(head2);
Node* mergedHead = MergeSortedList(head1, head2);
printf("Merged list: ");
PrintList(mergedHead);
return 0;
}
```
这段代码可以实现两个有序单链表的合并,时间复杂度为O(m+n),其中m和n分别是两个链表的长度。