链表--合并两个有序链表 Leetcode 21

题目

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

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路

迭代法

因为两个链表是有序的，因此只要按顺序比较两个链表结点即可，小的结点加入到新的链表中，直到两个链表其中一个为空，然后将不为空的链表接到新链表末尾即可。
时间复杂度O(m+n)，因为需要将两个链表遍历一遍
空间复杂度O(1)，无需额外的内存

c++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head=new ListNode(-1), *cur;

        cur = head;
        while(l1 != nullptr && l2 != nullptr){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }

        if(l1 == nullptr) cur->next = l2;
        else cur->next = l1;

        return head->next;
    }
};

递归法

采用递归的方法进行归并，假定现在两个链表当前结点都不为空，那么归并的公式为

l1的当前结点的值小于l2当前结点的值，那么归并结果为l1->next = merge(l1->next, l2)，即让l1后面的链表和l2链表进行归并，返回l1当前结点。
l1的当前结点的值大于等于l2当前结点的值，那么归并结果为l2->next = merge(l1, l2->next)，即让l1链表和l2后面的链表进行归并，返回l2当前结点。

当两个链表其中一个为空时，返回另一个链表即可。
时间复杂度O(m+n)
空间复杂度O(m+n)，因为有递归调用栈

c++代码

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr){
            return l2;
        }else if(l2 == nullptr){
            return l1;
        }

        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }