21. 合并两个有序链表

题目描述

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

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

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

迭代方法

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head=new ListNode(-1);//新定义结点
        ListNode *prev=head;
        while(l1!=nullptr && l2!=nullptr){
            if(l1->val<l2->val){//哪个小就指向那个
                prev->next=l1;
                l1=l1->next;
            }
            else{
                prev->next=l2;
                l2=l2->next;
            }
            prev=prev->next;
        }
        if(l1!=nullptr)prev->next=l1;//最后比较有非空则放在最后
        if(l2!=nullptr)prev->next=l2;
        return head->next;
    }

迭代的思路较为简单，只需要把较小的那个放在prev后面即可。

递归思路

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {//为空即终止
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {//l1小则元素取l1后面元素
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);//同理
            return l2;
        }
    }