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

本文涉及知识点　

• 哨兵结点的运用

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

1 Leetcode21 合并有序链表

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

示例1：

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

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

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

效果更好哈！

01 题目解析

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

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

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

今天小蓝没有把具体完整的画出来，想着做了一个带bgm的动画，大家可以放松放松的看看。

02 代码实现

1 c++版本

2 python版本

3 java版本