图解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;
    }
}