合并有序链表

[编程题]合并有序链表

热度指数：126418 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。

数据范围：链表长度 $0 \le n \le 1000 \$ ，链表中的值 $|val| \le 1000\$

要求：空间复杂度 $O(1)\$ ,时间复杂度 $O(n) \$

示例1

输入

{1},{2}

输出

{1,2}

示例2

输入

{2},{1}

输出

{1,2}

示例3

输入

{1,2,3},{}

输出

{1,2,3}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

漫漫云天自翱翔

发表于 2021-07-19 18:56:15

精华题解题解一创建辅助头节点图示：复杂度分析：时间复杂度：O(M+N))，最差为轮流插入两个链表，最终需要遍历完两个链表，所以为O(M+N)) 空间复杂度：O（1），只使用了有限常数个变量；实现如下： class Solution { public: /** * * @pa 展开全文

蒙牛麦片

发表于 2021-07-16 18:11:38

精华题解 NC33* 合并有序链表题意分析：将两个有序的链表合并题解一：我们新建4个指针，dummy用于返回最后结果，p用于遍历链表1，q用于遍历链表2，r用于指示生成的新链表末端。举个如下例子：开始拿指针p与指针q比较，指针p所指元素比较小，那么将r->next = p，p = p- 展开全文

ajaj

发表于 2021-07-13 17:29:59

精华题解思路: 从题中给出的有效信息：两个有序的链表合并后新链表有序故此两个有序的链表，合并两个链表可以使用递归和双指针的方式来解答方法一：递归具体做法：如果l1节点值比l2小，将 l1的下一个节点指向 l1.next 和 l2 合并后的头结点；l1节点值比l2小同理 import 展开全文

城志

发表于 2020-02-19 09:12:57

1. 先处理头结点 1.1 分析把两个链表中较小的头作为新链表的头依次比较两个链表未合并部分的头，较小者插入新表的尾处理未走到尽头的链表1.2 代码 public class Solution { public ListNode mergeTwoLists(ListNode l1, Li 展开全文

麻豆出品

发表于 2020-09-06 00:31:54

跟合并有序数组差不多套路，就是数据结构麻烦些。思路：先选出第一个节点，然后遍历两个链表，把小的作为当前节点的下一个节点，一直到其中一个链表遍历完，这时候把另一个链表直接接上。当然实现起来有递归和非递归版本，看你喜欢哪个啦，都没毛病，不过递归可能代码更短小精湛些。代码1（非递归版）： class L 展开全文