合并两个有序链表要求用递归的方法

Question

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

力扣 https://leetcode-cn.com/problems/merge-two-sorted-lists/

Answer 1

一、分析

1、分别考虑两个比较的头是不是空指针；
2、如果都不为空，则比较大小；
3、然后递归比较下一个节点即可；

二、源码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr) {
            return l2;
        }else if(l2 == nullptr) {
            return l1;
        }else {
            if(l1->val < l2->val) {
                l1->next = mergeTwoLists(l1->next, l2);
                return l1;
            }else {
                l2->next = mergeTwoLists(l1, l2->next);
                return l2;
            }
        }
        return nullptr;
    }
};