用C语言编写一个程序,实现有序线性链表的合并,合并后仍有序
时间: 2023-05-25 07:02:53 浏览: 97
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 定义链表指针类型
typedef ListNode* List;
// 创建链表节点
ListNode* createNode(int val) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
return node;
}
// 插入节点
void insertNode(List* head, int val) {
ListNode* node = createNode(val);
if (*head == NULL) {
*head = node;
return;
}
ListNode* p = *head;
while (p->next != NULL) {
p = p->next;
}
p->next = node;
}
// 输出链表
void printList(List head) {
ListNode* p = head;
while (p != NULL) {
printf("%d->", p->val);
p = p->next;
}
printf("NULL\n");
}
// 合并有序链表
List merge(List l1, List l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
ListNode* p1 = l1;
ListNode* p2 = l2;
List result = NULL;
ListNode* p = result;
while (p1 != NULL && p2 != NULL) {
if (p1->val <= p2->val) {
ListNode* node = createNode(p1->val);
if (result == NULL) {
result = node;
p = result;
}
else {
p->next = node;
p = p->next;
}
p1 = p1->next;
}
else {
ListNode* node = createNode(p2->val);
if (result == NULL) {
result = node;
p = result;
}
else {
p->next = node;
p = p->next;
}
p2 = p2->next;
}
}
while (p1 != NULL) {
ListNode* node = createNode(p1->val);
p->next = node;
p = p->next;
p1 = p1->next;
}
while (p2 != NULL) {
ListNode* node = createNode(p2->val);
p->next = node;
p = p->next;
p2 = p2->next;
}
return result;
}
int main() {
// 创建两个有序链表
List l1 = NULL;
insertNode(&l1, 1);
insertNode(&l1, 3);
insertNode(&l1, 5);
printf("链表l1:");
printList(l1);
List l2 = NULL;
insertNode(&l2, 2);
insertNode(&l2, 4);
insertNode(&l2, 6);
printf("链表l2:");
printList(l2);
// 合并有序链表
List result = merge(l1, l2);
printf("合并后的链表:");
printList(result);
return 0;
}
```
阅读全文