一、题目
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
二、示例
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)/ ~ 「干货分享，每天更新」
网友评论