两个有序链表合并(新表不含重复元素)只用C语言
时间: 2023-05-29 14:01:55 浏览: 82
假设我们有两个有序链表l1和l2,我们可以创建一个新链表l3,利用指针遍历l1和l2,并比较它们的元素值大小,把较小的元素加入l3中。如果两个元素的值相等,则只加入其中一个元素。最后,如果其中一个链表已经遍历完了,我们可以把另一个链表的剩余元素直接加入新链表中。
以下是用C语言实现这个算法的代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node* next;
} Node;
Node* merge_lists(Node* l1, Node* l2) {
// 创建新链表头结点
Node* head = NULL;
// 记录当前元素的指针
Node* current = NULL;
// 比较两个链表中元素大小,加入新链表
while (l1 != NULL && l2 != NULL) {
if (l1->value < l2->value) {
if (head == NULL) {
head = current = l1;
} else {
current->next = l1;
current = current->next;
}
l1 = l1->next;
} else if (l2->value < l1->value) {
if (head == NULL) {
head = current = l2;
} else {
current->next = l2;
current = current->next;
}
l2 = l2->next;
} else { // 两个元素相等
if (head == NULL) {
head = current = l1; // 只加入一个元素
} else {
current->next = l1; // 只加入一个元素
current = current->next;
}
l1 = l1->next;
l2 = l2->next;
}
}
// 把剩余元素加入新链表
if (l1 != NULL) {
if (head == NULL) {
head = l1;
} else {
current->next = l1;
}
} else if (l2 != NULL) {
if (head == NULL) {
head = l2;
} else {
current->next = l2;
}
}
return head;
}
void print_list(Node* head) {
while (head != NULL) {
printf("%d ", head->value);
head = head->next;
}
printf("\n");
}
int main() {
// 创建两个有序链表
Node* l1 = (Node*)malloc(sizeof(Node));
l1->value = 1;
Node* node1 = (Node*)malloc(sizeof(Node));
node1->value = 3;
l1->next = node1;
Node* node2 = (Node*)malloc(sizeof(Node));
node2->value = 5;
node1->next = node2;
node2->next = NULL;
Node* l2 = (Node*)malloc(sizeof(Node));
l2->value = 2;
Node* node3 = (Node*)malloc(sizeof(Node));
node3->value = 3;
l2->next = node3;
Node* node4 = (Node*)malloc(sizeof(Node));
node4->value = 4;
node3->next = node4;
Node* node5 = (Node*)malloc(sizeof(Node));
node5->value = 6;
node4->next = node5;
node5->next = NULL;
// 合并两个链表
Node* merged = merge_lists(l1, l2);
print_list(merged);
// 释放内存
free(l1);
free(node1);
free(node2);
free(l2);
free(node3);
free(node4);
free(node5);
free(merged);
return 0;
}
```
输出:
```
1 2 3 4 5 6
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)