已知两个长度分别为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;
}

相关问题

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

要合并两个升序单链表 L1 和 L2，使其成为一个降序单链表 L，你需要遍历两个链表并将较大的节点添加到新链表中。由于 L1 和 L2 都是升序的，所以从头开始比较即可得到最大值。以下是一个简单的 C++ 实现：

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeSortedLists(ListNode* head1, ListNode* head2) {
    ListNode* dummy = new ListNode(0); // 创建虚拟头结点
    ListNode* tail = dummy;            // 尾指针指向虚拟头

    while (head1 && head2) {           // 只有当两个链表都有节点时循环
        if (head1->val > head2->val) {
            tail->next = head1;
            head1 = head1->next;
        } else {
            tail->next = head2;
            head2 = head2->next;
        }
        tail = tail->next;              // 更新尾指针
    }

    // 如果其中一个链表为空，将另一个链表剩余的部分连接到结果链表末尾
    if (head1) {
        tail->next = head1;
    } else {
        tail->next = head2;
    }

    return dummy->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;
}