Day108 | 灵神 | 合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

思路：

这是道easy题，直接写就行

说一下递归的写法

递归函数的含义是合并两个有序链表，返回值是合并后的链表的头结点

递归边界：如果其中一个链表为空，直接返回另一个链表作为合并后的结果

本层逻辑：谁小就把谁接到当前结点的后面，然后返回当前结点作为合并后的结果

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *t=new ListNode;
        ListNode *res=t;
        while(list1&&list2)
        {
            if(list1->val<list2->val)
            {
                t->next=list1;
                list1=list1->next;
            }
            else
            {
                t->next=list2;
                list2=list2->next;
            }
            t=t->next;
        }
        t->next=list1?list1:list2;
        return res->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2; // 注：如果都为空则返回空
        if (list2 == nullptr) return list1;
        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
};