力扣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 -> 5
    struct ListNode* list1 = createNode(1);
    list1->next = createNode(3);
    list1->next->next = createNode(5);

    // 创建第二个有序链表: 2 -> 4 -> 6
    struct 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;
}