题解 | #合并有序链表#

NC33* 合并有序链表

题意分析：

将两个有序的链表合并

题解一：

我们新建4个指针，dummy用于返回最后结果，p用于遍历链表1，q用于遍历链表2，r用于指示生成的新链表末端。

举个如下例子：

图片说明

开始拿指针p与指针q比较，指针p所指元素比较小，那么将r->next = p，p = p->next，r = r->next,r->next = NULL。链表变化如下：

图片说明

重复步骤1，拿指针p与指针q比较，指针q所指元素比较小，那么将r->next=q，q = q->next，r = r->next，r->next = NULL。链表变化如下
重复以上步骤，直到p为空或者q为空，把不为空的链表追加到指针r之后。

代码实现如下

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* r = dummy;
        while (l1&&l2){
                          //当l1和l2均不为空，合并
            if (l1->val < l2->val) {
                r->next = l1;
                l1 = l1->next;
                r = r->next;
                r->next = NULL;
            }
            else {
                r->next = l2;
                l2 = l2->next;
                r = r->next;
                r->next = NULL;
            }
        }
              //在合并结束后，吧没有合并的部分追加到r之后
        if (l1)
            r->next = l1;

        if (l2)
            r->next = l2;
        return dummy->next;
    }

时间复杂度： $O(m+n)$ ，m，分别为两个链表的长度

空间复杂度： $O(1)$ 。