图解LeetCode——剑指 Offer 25. 合并两个排序的链表

一、题目

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

二、示例

2.1> 示例1：

【输入】1->2->4, 1->3->4
【输出】1->1->2->3->4->4

限制：

• 0 <= 链表长度 <= 1000

三、解题思路

根据题目描述，我们可以过滤出解题的关键词：

【关键词1】“两个递增排序...”：由于题目要求最终拼装的结果也是递增排序的，那么我们就不需要对每个链表在进行排序了。
【关键词2】“合并这两个链表”：既然两个都是链表，我们就只能通过next来一个个的遍历和对比链表中的节点，那么针对这两个链表，我们需要创建两个指针，分别执行各自链表需要对比的节点位置（下图中的l1和l2）。

那么这道题其实思路不难，比较麻烦的点是合并特殊的链表，例如：

【麻烦1】如果第1个链表的首节点小于等于第2个链表的首节点，那么结果链表的首节点就是第1个链表的首节点，否则就是第2个链表的首节点。
【麻烦2】需要考虑如果两个待合并的链表都为空的情况；
【麻烦3】需要考虑其中只有一个链表是空的情况；
【麻烦4】两个链表都不为空，但是链表的长度不同，就会有一个链表先遍历完毕，那么另一个链表只需要拼装到结果末尾即可，不需要再次遍历。

针对上面的麻烦点，我们可以通过各种的if判断来进行处理，但是，还是有一个比较巧妙的方法，就是创建一个空值的节点作为结果链表的首节点，即：ListNode result = new ListNode()；，那么我们后续对比两个链表时，都是向result节点后面进行链表的拼装，最终返回结果的时候只需要返回result.next即可。下图是具体的处理过程，因为逻辑处理比较简单，所以仅抽取了两次操作进行了图解，并没有把所有操作都画出来。

 

四、代码实现

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode result = new ListNode(), temp = result;while(l1 != null && l2 != null) {if (l1.val <= l2.val) {temp.next = l1;l1 = l1.next;} else {temp.next = l2;l2 = l2.next;}temp = temp.next;}if (l1 == null) temp.next = l2;if (l2 == null) temp.next = l1;return result.next;}
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」