漫画：如何合并两个有序链表

01

题目分析

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

示例：

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

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

首先我们拿到题目乍眼一看，类似这种链表的合并问题。基本上马上可以想到需要设置一个哨兵节点，这可以在最后让我们比较容易地返回合并后的链表。（不懂哨兵节点的同学，可以先移驾到 删除链表倒数第N个节点 进行学习）

假设我们的链表分别为:

l1 = [1,2,4]

l2 = [1,3,4]

同时我们设定一个"prehead"的哨兵节点,大概是下面这样：

02

题目图解

如上图所示，首先我们维护一个 prehead 的哨兵节点。我们其实只需要调整它的 next 指针。让它总是指向l1或者l2中较小的一个，直到l1或者l2任一指向null。这样到了最后，如果l1还是l2中任意一方还有余下元素没有用到，那余下的这些元素一定大于prehead已经合并完的链表（因为是有序链表）。我们只需要将这些元素全部追加到prehead合并完的链表后，最终就得到了我们需要的链表。大概流程如下图：

1.首先我们将prehead指向l1或者l2中比较小的一个。如果相等，则任意一个都可以。此时的l1位[2,4]，l2位[1,3,4]

2.我们继续上面的步骤。将prehead的链表指向l1和l2中较小的一个。现在这里就是指向1。

3.反复上图步骤

4.现在prehead.Next就是我们需要的链表。

03

Go语言示例

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    prehead := &ListNode{}
    result := prehead
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            prehead.Next = l1
            l1 = l1.Next
        }else{
            prehead.Next = l2
            l2 = l2.Next
        }
        prehead = prehead.Next
    }
    if l1 != nil {
        prehead.Next = l1
    }
    if l2 != nil {
        prehead.Next = l2
    }
    return result.Next
}

注：本系列所有教程中都不会用到复杂的语言特性，大家不需要担心没有学过go。算法思想最重要，使用go纯属本人爱好。同时，本系列所有代码均在leetcode上进行过测试运行，保证其严谨性！