21.合并两个有序链表

roydonGuo

发布于 2022-11-02 15:56:16

1460

发布于 2022-11-02 15:56:16

文章被收录于专栏：posts

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

示例 1：

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

示例 2：

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

示例 3：

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

C
思路

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

使用递归：一直进行比较直到其中一个链表值为NULL，此为判断递归结束条件。然后开始返回，是在原有链表的基础之上往后面拼接节点。递归到最后一层才开始拼接链表。