将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。用C语言
时间: 2024-09-15 08:02:46 浏览: 39
c代码-将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
在C语言中,将两个升序链表合并成一个新的升序链表可以采用迭代或递归的方式实现。这里是一个简单的迭代方法示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 创建新的链表节点
ListNode* createNode(int val) {
ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 合并两个升序链表
ListNode* mergeSortedLists(ListNode* list1, ListNode* list2) {
// 定义三个指针分别指向当前遍历到的位置
ListNode *result = NULL, *p1 = list1, *p2 = list2;
// 当任意一个链表还有节点,或者两个链表都有节点时
while ((p1 != NULL && p2 != NULL) || (p1 != NULL && p2 == NULL) || (p1 == NULL && p2 != NULL)) {
// 如果list1的值小于等于list2的值,添加list1的节点到结果链表
if (p1 != NULL && (p2 == NULL || p1->val <= p2->val)) {
result = result ? result : list1; // 如果result非空,就将list1插入到中间
result->next = createNode(p1->val);
p1 = p1->next;
} else { // 否则,添加list2的节点
result = result ? result : list2;
result->next = createNode(p2->val);
p2 = p2->next;
}
}
// 添加剩余的链表节点,如果有的话
if (p1 != NULL) {
result->next = p1;
} else if (p2 != NULL) {
result->next = p2;
}
return result;
}
// 打印链表
void printList(ListNode* head) {
while (head) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
int main() {
// 创建测试链表
ListNode* list1 = createNode(1);
list1->next = createNode(4);
list1->next->next = createNode(5);
ListNode* list2 = createNode(1);
list2->next = createNode(3);
list2->next->next = createNode(4);
// 合并并打印结果
ListNode* mergedList = mergeSortedLists(list1, list2);
printList(mergedList);
return 0;
}
```
这个程序会合并`list1`和`list2`两个升序链表,并打印出合并后的结果。注意,这个实现假设输入链表已经是升序排列的。
阅读全文