我要招人

去企业版

首页 > 试题广场 >

合并两个排序的链表

[编程题]合并两个排序的链表

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

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

数据范围： $0 \le n \le 1000$ ， $-1000 \le 节点值 \le 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}，转换过程如下图所示：

示例1

输入

{1,3,5},{2,4,6}

输出

{1,2,3,4,5,6}

示例2

输入

{},{}

输出

{}

示例3

输入

{-1,2,4},{1,3,4}

输出

{-1,1,2,3,4,4}

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

算法知识视频讲解

Maokt

发表于 2021-06-24 14:26:26

精华题解算法思想一：迭代解题思路：设置result为哑结点，放置于新链表之前，最后返回的就是result.next；设置cur为当前节点，从result开始当两个链表都非空时进入循环，令新链表的下一个节点cur.next为val更小的节点，相应的链表节点后移一位，每次循环记得cur也要后移展开全文

开车的阿Q

发表于 2021-06-27 23:03:04

精华题解描述这是一篇面对初级coder的题解。知识点：链表难度：二星题解题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。考察链表的基础知识方法一：采用新链表合并思路：创建一个新链表，将两个旧链表按顺序合展开全文

牛客题解官

发表于 2020-05-29 15:15:28

描述这是一篇针对初学者的题解，共用2种方法解决。知识点：单链表，递归难度：一星题解：题目要求：给两个非递减单链表l1, l2，合并为一个非递减的单链表。方法一：迭代版本求解初始化：定义cur指向新链表的头结点操作：如果l1指向的结点值小于等于l2指向的结点值，则将l1指向的结点值链接展开全文

NiimiSora

发表于 2021-09-18 17:37:46

递归思路同Leetcode 21 Merge Two Sorted Lists ，用递归实现：简单地理一下思路：从头结点开始考虑，比较两表头结点的值，值较小的list的头结点后面接merge好的链表（进入递归了）；若两链表有一个为空，返回非空链表，递归结束；当前层不考虑下一层的细节，当前展开全文

小明同学#

发表于 2019-09-22 21:12:28

public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { & 展开全文

牛客题解官

发表于 2022-04-22 11:21:51

题目的主要信息：两个元素值递增的链表，单个链表的长度为nnn 合并这两个链表并使新链表中的节点仍然是递增排序的举一反三：学习完本题的思路你可以解决如下题目： JZ23.链表中环的入口节点 JZ22.链表中倒数最后k个节点 JZ52.两个链表的第一个公共节点方法一：双指针迭代（推荐使用）展开全文

Dogemeat

发表于 2021-09-28 15:35:56

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public 展开全文

郭家兴0624

发表于 2019-08-10 14:57:45

题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。非递归方法： def Merge(self, l1, l2): dummy = cur = ListNode(0) while l1 and l2: if l1.val 展开全文

年少挽剑世无双·

发表于 2020-03-06 17:51:09

题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。解答：1.遍历两个链表，按大小顺序拼接。public class Q_16 { public ListNode Merge(ListNode list1, ListNode list2) { 展开全文