力扣6-合并两个有序链表

一.题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

二.代码

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if(list1==NULL){return list2;}else if(list2==NULL){return list1;}else if(list1->val<list2->val){list1->next=mergeTwoLists(list1->next,list2);return list1;}else{list2->next=mergeTwoLists(list1,list2->next);return list2;}
}

三.代码解读

• 如果 list1 为 NULL，说明第一个链表为空，此时直接返回 list2，因为合并后的结果就是第二个链表。
• 如果 list2 为 NULL，说明第二个链表为空，此时直接返回 l1，因为合并后的结果就是第一个链表。
• 接下来比较 list1 和 list2 的当前节点的值（通过 list1->val 和 list2->val）：
  • 如果 list1 的当前节点的值小于 list2 的当前节点的值，那么递归调用 mergeTwoLists 函数，将 list1 的下一个节点和 list2 作为新的参数传递进去，并将结果赋值给 list1 的下一个节点（list1->next = mergeTwoLists(list1->next, list2);），然后返回 list1 作为合并后的链表的头节点。
  • 反之，如果 list2 的当前节点的值小于等于 list1 的当前节点的值，那么递归调用 mergeTwoLists 函数，将 list1 和 list2 的下一个节点作为新的参数传递进去，并将结果赋值给 list2 的下一个节点（list2->next = mergeTwoLists(list1, list2->next);），然后返回 list2 作为合并后的链表的头节点。

四.补全代码

​
#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
struct ListNode {int val;struct ListNode* next;
};// 合并两个有序链表的函数
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if (list1 == NULL){return list2;}else if (list2 == NULL){return list1;}else if (list1->val < list2->val){list1->next = mergeTwoLists(list1->next, list2);return list1;}else{list2->next = mergeTwoLists(list1, list2->next);return list2;}
}// 创建新节点
struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = val;newNode->next = NULL;return newNode;
}// 打印链表
void printList(struct ListNode* head) {struct ListNode* curr = head;while (curr!= NULL) {printf("%d ", curr->val);curr = curr->next;}printf("\n");
}// 释放链表内存
void freeList(struct ListNode* head) {struct ListNode* temp;while (head!= NULL) {temp = head;head = head->next;free(temp);}
}int main() {// 创建第一个有序链表: 1 -> 3 -> 5struct ListNode* list1 = createNode(1);list1->next = createNode(3);list1->next->next = createNode(5);// 创建第二个有序链表: 2 -> 4 -> 6struct ListNode* list2 = createNode(2);list2->next = createNode(4);list2->next->next = createNode(6);// 合并两个链表struct ListNode* mergedList = mergeTwoLists(list1, list2);// 打印合并后的链表printf("Merged List: ");printList(mergedList);// 释放内存freeList(mergedList);return 0;
}