21 合并两个排序的链表

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

题目

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的

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

数据结构

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

解法：迭代

普通

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *result = nullptr; //存放最终结果
        ListNode *r = nullptr; //新链表的指针

        auto p = l1; //l1的指针
        auto q = l2; //l2的指针

        while(p!=nullptr && q!=nullptr) { //两个都不为空
            ListNode* next = nullptr; //新链表的下一个

            //比大小
            if(p->val <= q->val) {
                next = p;
                p = p->next;
            }
            else {
                next = q;
                q = q->next;
            }

            //挂接
            if(result == nullptr) { //第一个
                result = r = next;
            } else { //不是第一个
                r->next = next;
                r = r->next; //注意位移
            }
        }

        //l1、l2可能有剩下的元素，与上面一样处理
        ListNode* next = nullptr;

        if(p!=nullptr) {
            next = p;
        }
        if(q!=nullptr) {
            next = q;
        }

        if(result == nullptr) {
            result = next;
        } else {
            r->next = next;
        }

        return result;
    }
};

预设起始节点

预先设置一个起始节点，防止初始条件下判空的操作。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //临界条件
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;

        //增加一个head，后续就无需判断起始节点是否为nullptr
        ListNode head(-1);
        auto h = &head;

        while(l1!=nullptr && l2!=nullptr) { //两个都不为空
            //比较大小，并挂接
            if(l1->val <= l2->val) {
                h->next = l1;
                l1 = l1->next;
            }
            else{
                h->next = l2;
                l2 = l2->next;
            }

            h = h->next;
        }

        //注意，可能还有剩余
        if(l1!=nullptr) {
            h->next = l1;
        }
        if(l2!=nullptr) {
            h->next = l2;
        }

        return head.next;
        //head是栈上的内存，无需释放
    }
};

【时间复杂度】两个链表都遍历了一遍，O(n+m)

【空间复杂度】常数级别，即O(1)

解法：递归

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 = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else
        {
            //此次计算，首节点是l2
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

【时间复杂度】两个链表都遍历了一遍，O(n+m)

【空间复杂度】递归需要消耗栈空间，栈空间的大小取决于递归深度。如果输入数据很不好，最多可能调用n+m次，因此空间复杂度为O(n+m)