[算法专题 ] 合并两个有序链表

快来打我* 2023-09-30 14:23 5阅读 0赞

**目录**

描述:

效果:

思路:

代码:

链表

虚拟节点

尾节点

--------------------

### 描述: ###

> 将两个升序链表合并为一个新的 **升序** 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

### 效果: ###

>     输入：l1 = [1,2,4], l2 = [1,3,8]
>     输出：[1,1,2,3,4,8]

### 思路: ###

> 我们可以用迭代技巧来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果，当一个节点被添加到结果后，将对应链表中的节点向后移动一位。

### 代码: ###

> class Method\{  
> public ListNode mergeTwoLists(ListNode l1, ListNode l2) \{  
> ListNode head= new ListNode(-1);
> 
> ListNode prev = head;  
> while (l1 != null && l2 != null) \{  
> if (l1.val <= l2.val) \{  
> prev.next = l1;  
> l1 = l1.next;  
> \} else \{  
> prev.next = l2;  
> l2 = l2.next;  
> \}  
> prev = prev.next;  
> \}
> 
> // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可  
> prev.next = l1 == null ? l2 : l1;
> 
> return head.next;  
> \}  
> \}

#### **链表** ####

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

链表适合在数据需要有一定顺序，但是又需要进行频繁增删除的场景。

头结点：在单链表的第一个结点(有效元素)之前附设的一个结点，称之为头结点。  
头指针：指向头结点的指针称为头指针。  
首节点(首元结点)：首节点就是第一个元素(头元素)的结点

#### **虚拟节点** ####

定义：数据结构中，在链表的第一个结点之前附设一个结点，它没有直接前驱，称之为虚拟结点。虚拟结点的数据域可以不存储任何信息，虚拟结点的指针域存储指向第一个结点的指针。

作用：对链表进行增删时统一算法逻辑，减少边界处理（避免了判断是否是空表或者是增删的节点是否为第一个节点）

#### **尾节点** ####

定义：数据结构中，尾结点是指链表中最后一个节点，即存储最后一个元素的节点。

作用：由于移动到链表末尾需要线性的时间，因此在链表末尾插入元素会很耗时， 增加尾节点便于在链表末尾以 O(1) 的时间插入元素。

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-合并两个有序链表

1. 合并两个有序链表将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1->2->4, 1->3->...

分手后的思念是犯贱/ 2024年04月18日 07:34/ 0 赞/ 70 阅读

相关 [算法专题 ] 合并两个有序链表

目录描述: 效果: 思路: 代码: 链表虚拟节点尾节点 -------------------- 描述: > 将两个升序链表合并为一个新的升序

快来打我*/ 2023年09月30日 14:23/ 0 赞/ 6 阅读

相关合并两个有序链表

一思路按老师上课讲的，先用其他链表记录两个链表共有部分，然后判断谁null，再接上另一个二代码 class Solution(object):

爱被打了一巴掌/ 2023年07月13日 10:51/ 0 赞/ 10 阅读

相关合并两个有序链表

合并两个有序链表 1、题目题目要求：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输

灰太狼/ 2023年03月01日 12:52/ 0 赞/ 9 阅读

相关 leetcode算法题--合并两个有序链表

题目概述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

末蓝、/ 2022年11月26日 01:44/ 0 赞/ 175 阅读

相关链表----21. 合并两个有序链表

【题目】将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1： ![在这里插入图片描述][watermark_typ

「爱情、让人受尽委屈。」/ 2022年11月16日 01:54/ 0 赞/ 223 阅读

相关合并两个链表c++_21 合并两个有序链表

01 题目信息 > 题目地址: > > https://leetcode-cn.com/problems/merge-two-sorted-lists/

朴灿烈づ我的快乐病毒、/ 2022年10月25日 04:52/ 0 赞/ 221 阅读

相关算法：合并两个有序链表

1. 题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 e.g 输入：l1 = \[1,2,5\], l2 =

雨点打透心脏的1/2处/ 2022年10月14日 05:53/ 0 赞/ 212 阅读

相关合并两个有序链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

向右看齐/ 2022年09月01日 12:56/ 0 赞/ 233 阅读

相关合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输入：1->2->4, 1->3->4

我会带着你远行/ 2021年10月30日 08:20/ 0 赞/ 350 阅读