剑指 Offer 25. 合并两个排序的链表

力扣

创建一个伪头节点，然后循环比较l1和l2的val值哪个小就添加哪个到链表后面。最后使最后一个节点的next指针指向不为空的链表。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummyNode=new ListNode(0),*cur=dummyNode;
        while(l1&&l2){
            if(l1->val<=l2->val){
                cur->next=l1;
                l1=l1->next;
            }else{
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
        }
        cur->next=l1==nullptr?l2:l1;
        return dummyNode->next;
    }
};

找到当前最小的一个节点添加进链表，然后next指向当前最小节点的下一个节点和另一个链表的merge。递归终止条件是l1和l2其中一个为空指针。

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