将两个递增有序的单链表的合并为一个递增有序的单链表并返回头指针C语言代码
时间: 2024-09-28 19:17:10 浏览: 50
线性表的应用-线性表教程
在C语言中,将两个递增有序的单链表合并成一个新的递增有序链表可以使用迭代或递归的方式。这里是一个使用迭代的例子:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct ListNode {
int val; // 节点值
struct ListNode *next; // 指向下一个节点的指针
} ListNode;
// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 创建新的链表头节点
ListNode* head = NULL;
// 初始化当前节点为l1或l2,取决于哪一个链表为空或较大
ListNode* cur = (l1 && l2 && l1->val <= l2->val) ? l1 : l2;
// 迭代合并
while (l1 && l2) {
if (l1->val <= l2->val) {
// 如果l1较小,添加到新链表,并移动l1指针
if (!head) {
head = l1;
} else {
head->next = l1;
}
l1 = l1->next;
} else {
// 如果l2较小,添加到新链表,并移动l2指针
if (!head) {
head = l2;
} else {
head->next = l2;
}
l2 = l2->next;
}
}
// 添加剩余的链表(如果还有)
if (l1) {
head->next = l1;
} else if (l2) {
head->next = l2;
}
return head;
}
// 测试函数
void printList(ListNode* head) {
while (head) {
printf("%d -> ", head->val);
head = head->next;
}
printf("NULL\n");
}
int main() {
// 创建示例链表
ListNode* list1 = (ListNode*)malloc(sizeof(ListNode));
list1->val = 1;
list1->next = (ListNode*)malloc(sizeof(ListNode));
list1->next->val = 4;
list1->next->next = NULL;
ListNode* list2 = (ListNode*)malloc(sizeof(ListNode));
list2->val = 2;
list2->next = (ListNode*)malloc(sizeof(ListNode));
list2->next->val = 5;
list2->next->next = NULL;
// 合并链表
ListNode* mergedList = mergeTwoLists(list1, list2);
// 打印合并后的链表
printList(mergedList);
return 0;
}
```
运行这个程序,你会看到合并后的链表结果是 `1 -> 2 -> 4 -> 5 -> NULL`。
阅读全文