合并两个排序的链表 迭代+递归(rust+cpp)

BM4 合并两个排序的链表

描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤𝑛≤10000≤n≤1000，−1000≤节点值≤1000−1000≤节点值≤1000要求：空间复杂度 𝑂(1)O(1)，时间复杂度 𝑂(𝑛)O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

思路

1. 递归方法： 如果其中一个链表为空，直接返回另一个链表。比较两个链表当前节点的值，将较小节点作为合并后链表的头节点。递归地将剩余部分的链表进行合并，将结果连接到当前节点的后面。返回合并后的链表。
2. 迭代方法： 创建一个新的虚拟头结点(dummy node)作为合并后链表的头部。使用一个指针指向新链表的当前节点，初始时指向虚拟头结点。遍历两个输入链表，比较当前节点的值，将较小的节点接在当前节点后面，并移动到下一个节点。如果其中一个链表已经遍历完，将另一个链表的剩余部分直接接在新链表的末尾。返回虚拟头结点的下一个节点作为合并后的链表。

不管是用哪一种方法实现，核心的思路都是取得两个链表中较小值得结点插入到新链表中，最后得出得新链表就是有序得；

图解

• 初始状态:

• 比较两个链表第一个结点值

• p1->next和p2比较

• p1->next和p2->next比较

• 以此类推，最终的比较结果

代码实现

• C++

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
    // 递归，每次合在头节点添加一个较小的结点
    if (pHead1 == nullptr) return pHead2;
    if (pHead2 == nullptr) return pHead1;
    // 创建一个新的链表，用来表示合并后的新链表；
    ListNode* mHead = nullptr;
    if (pHead1->val < pHead2->val) 
    {
        mHead = pHead1;
        mHead ->next = Merge(pHead1 -> next,pHead2);
    } else 
    {
        mHead  = pHead2;
        mHead->next = Merge(pHead1,pHead2 ->next);
    }
    return mHead;
}

// 迭代实现
ListNode* Merg