【牛客刷题 - 算法】加精 _ 合并两个有序的链表 - 从思路设计、bug 排除到最终实现的全过程

作者：清风莫追

2022 年 10 月 06 日
湖南
本文字数：2027 字
阅读完需：约 7 分钟

个人主页-CSDN：CSDN清风莫追
🔥 该专栏作为刷题笔记，持续更新中。
推荐一款面试、刷题神器牛客网：👉开始刷题学习👈

1.题目描述

描述

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

数据范围： 0≤n≤1000，−1000≤节点值≤1000

要求：空间复杂度 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}，转换过程如下图所示：

2.算法设计思路

1）总体思路：

以原链表中的值，新建一个链表，并保持有序。

如果直接将原链表中的结点接过来，问题会变得麻烦很多。我以前做过一次直接转移结点的，可参考：合并两个有序单链表，对象析构这一着我实在没想到

2）算法过程：

新建一个头指针 p，指向空。
使用两个指针 p1 和 p2 分别指向两个链表的头部，然后同时遍历两个链表。
每次遍历，创建一个新的结点连接到新链表尾部，然后比较 p1 和 p2 指向的结点中元素的值，并将较小的一个值存放到新结点中，同时相应的指针（p1 或 p2）向后移动一步。
停止遍历条件：p1 为空或 p2 为空。
将原链表中剩余元素的值转移到新链表中（如果有的话）。

3）遇到问题：

第一个结点的处理： 在创建新结点时，新链表可以处于两种状态：为空或不为空，因此需要分别考虑。

    if(p ** nullptr){                p = t;                pHead = p;            }else{                p->next = t;                p = p->next;            }

复制代码

原链表为空： 如果初始恰有一个原链表为空（另一个不为空），就会直接到第 5 步，转移原链表中的剩余元素，而此时新链表的头结点尚为空，操作p->next 就会出现问题。

//初始代码    while(p3 != nullptr){            p->next = new ListNode(0);            p = p->next;            p->val = p3->val;            p3 = p3->next;        }

复制代码

可以仿照问题 1 的方式，加一个分支判断。

//修改方案一//p3:指向第一个剩余的元素    while(p3 != nullptr){            if(p ** nullptr){                p = new ListNode(0);                pHead = p;            }else{                p->next = new ListNode(0);                p = p->next;            }            p->val = p3->val;            p3 = p3->next;        }

复制代码

但这样的代码看起来比较难看。我们也可以在函数头部打个下面这样的“补丁”。

//修改方案二    if(pHead1 ** nullptr){            return pHead2;        }else if(pHead2 ** nullptr){            return pHead1;        }

复制代码

4）尝试优化代码

代码优化我目前觉得主要有两个方面：运行效率与可读性。我比较希望代码可以集中地的展现思路、更加简练。

例如，关于遍历过程移动链表指针的操作，对比一下下面两段代码：

//代码段一            if(x1 < x2){                p1 = p1->next;            }else{                p2 = p2->next;            }

复制代码

//代码段二            ListNode** p3 = x1 < x2 ? &p1 : &p2;            *p3 = (*p3)->next;

复制代码

我会比较喜欢第二段代码，因为它移动指针的操作就集中在一步：*p3 = (*p3)->next; 。

3.算法实现

注：这里并不是完整代码，而只是核心代码的模式

最终代码，C++实现：

/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x) :            val(x), next(NULL) {    }};*/class Solution {public:    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {        if(pHead1 ** nullptr){            return pHead2;        }else if(pHead2 ** nullptr){            return pHead1;        }
        ListNode* pHead = nullptr;        ListNode* p = nullptr;        ListNode* p1 = pHead1;        ListNode* p2 = pHead2;
        while(p1 != nullptr && p2 != nullptr){            ListNode* t = new ListNode(0);            int x1 = p1->val;            int x2 = p2->val;
            t->val = x1 < x2 ? x1 : x2;            if(p ** nullptr){                p = t;                pHead = p;            }else{                p->next = t;                p = p->next;            }
            ListNode** p3 = x1 < x2 ? &p1 : &p2;            *p3 = (*p3)->next;        }
        ListNode* p3 = nullptr;        p3 = p1 != nullptr ? p1 : p2;
        while(p3 != nullptr){            p->next = new ListNode(0);            p = p->next;            p->val = p3->val;            p3 = p3->next;        }        return pHead;    }};

复制代码

4.运行结果

成功通过！

结束语：

今天的分享就到这里啦，快来一起刷题叭！👉开始刷题学习👈

感谢阅读

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/4f322d0911b30c428f9e15c24】。文章转载请联系作者。

清风莫追

关注

还未添加个人签名 2022.08.09 加入

编程一学生

发布

暂无评论

创作场景

【牛客刷题 - 算法】加精 _ 合并两个有序的链表 - 从思路设计、bug 排除到最终实现的全过程

1.题目描述

2.算法设计思路

1）总体思路：

2）算法过程：

3）遇到问题：

4）尝试优化代码

3.算法实现

4.运行结果

结束语：

清风莫追

评论