[leetcode链表系列]4 合并有序链表

[leetcode链表系列]4 合并有序链表

·1

本文涉及知识点

哨兵结点的运用

链表数据结构中哨兵的作用在之前详细阐述了[leetcode链表系列]2 删除链表中的节点，忘记了的小伙伴复习后再看效果一定翻倍哟！

1Leetcode21 合并有序链表

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

示例1：

输入：1->2->4, 1->3->4

输出：1->1->2->3->4->4

小蓝希望大家在此思考1分钟，

效果更好哈！

0

1

题目解析

思路为了方便返回合并后的链表，我们使用head为头结点，p1,p2分别跟踪两链表L1,L2.如下图。

如果p1当前值小于p2的值，我们就将p1的值直接连接在pre后面并移动p1。同样如果p1当前值大于p2的值，我们将p2的值连接在pre后面并移动p2。

循环结束的时候，如果有一个链表非空，因为两链表均有序，将其合并到另个链表即可。

0

2

代码实现

1c++版本

2python版本

3java版本

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。