一、题目

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

示例

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

二、解决方法

思路:首先,我们设定一个哨兵节点 "head" ,这个设定可以在最后让我们比较容易地返回合并后的链表。定义一个 pNew 指针指向哨兵节点 "head" ,我们需要做的是调整它的 next 指针。然后,我们重复以下过程,直到 l1 或者 l2 指向了 null :如果 l1 当前位置的值小于等于 l2 ,我们就把 l1 的值接在 prev 节点的后面同时将 l1 指针往后移一个。否则,我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面,我们都把 prev 向后移一个元素。在循环终止的时候, l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的,所以不管哪个链表是非空的,它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面,并返回合并后链表。

代码

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* pNew = head;
    while (l1 != NULL && l2 != NULL)
    {
        if (l1->val <= l2->val)
        {
            pNew->next = l1;
            l1 = l1->next;
        }
        else
        {
            pNew->next = l2;
            l2 = l2->next;
        }
        pNew = pNew->next;
    }
    pNew->next = l1 == NULL ? l2 : l1;

    return head->next;
}

复杂度分析

  • 时间复杂度:O(n+m)O(n + m) 。因为每次循环迭代中,l1 和 l2 只有一个元素会被放进合并链表中, while 循环的次数等于两个链表的总长度。所有其他工作都是常数级别的,所以总的时间复杂度是线性的
  • 空间复杂度:O(1)O(1) 。迭代的过程只会产生几个指针,所以它所需要的空间是常数级别的