已知两个长度分别为m、n（m、n均大于0）的升序单链表l1和l2，设计一个算法将它们的所有节点合并为一个长度为m+n的降序单链表l。

算法步骤如下：

1. 定义一个新的链表头节点head，以及一个指向head的指针p。

2. 从l1和l2的头节点开始，比较两个节点的值大小，将值较大的节点插入到head节点之后，然后将p指针指向新插入的节点。

3. 重复步骤2，直到l1或l2中的一个链表遍历完毕。

4. 将l1或l2中剩余的节点依次插入到head节点之后，直到两个链表都遍历完毕。

5. 返回head节点的下一个节点，即为合并后的降序单链表l。

代码实现如下：

ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode* head = new ListNode();
    ListNode* p = head;
    while (l1 && l2) {
        if (l1->val > l2->val) {
            p->next = l1;
            l1 = l1->next;
        } else {
            p->next = l2;
            l2 = l2->next;
        }
        p = p->next;
    }
    p->next = l1 ? l1 : l2;
    return head->next;
}

相关问题

已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。

将两个链表连接在一起，实际上就是将 L2 链接到 L1 的末尾。因为已经给出了链表的长度 m 和 n，因此可以先遍历 L1 到其末尾，然后将 L2 连接到 L1 的末尾即可。时间复杂度为 $O(m)$。

下面是算法的具体实现（C++ 代码）：

ListNode* joinTwoLists(ListNode* L1, ListNode* L2) {
    if (L1 == NULL) {
        return L2;
    }
    ListNode* p = L1;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = L2;
    return L1;
}

其中，ListNode 是链表节点的结构体，包含一个值 val 和一个指向下一个节点的指针 next。L1 和 L2 分别是两个链表的头节点指针。

已知两个带头节点的单链表l1和l2中的结点值均已按升序排序，设计一个算法，将l1和l2就地合并成一个升序的带头节点单链表,合并之后l1和l2单链表为空，并用l3记录新的带头节点单链表的头指针。

算法步骤如下：

1. 定义三个指针p1、p2、p3，分别指向l1、l2、l3的头节点；

2. 比较p1和p2所指节点的值，将较小值的节点接到p3的后面，并将p3指向新加入的节点；

3. 将p1或p2指向下一个节点，重复步骤2，直到p1或p2为空；

4. 将p1或p2剩余的节点接到p3的后面；

5. 返回l3的头指针。

代码实现如下：

ListNode* mergeList(ListNode* l1, ListNode* l2) {
    ListNode* p1 = l1->next;
    ListNode* p2 = l2->next;
    ListNode* p3 = new ListNode(); // 新链表的头节点
    ListNode* tail = p3; // 记录新链表的尾节点

    while (p1 && p2) {
        if (p1->val <= p2->val) {
            tail->next = p1;
            p1 = p1->next;
        } else {
            tail->next = p2;
            p2 = p2->next;
        }
        tail = tail->next;
    }

    if (p1) tail->next = p1;
    if (p2) tail->next = p2;

    l1->next = nullptr;
    l2->next = nullptr;
    ListNode* l3 = p3->next;
    delete p3;
    return l3;
}