让我们一起啃算法----合并两个有序链表

合并两个有序链表（Merge-Two-Sorted-Lists）

题干如下：

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

示例：

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

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

来源：力扣

这个题目和 两数相加 相似，都是考察对链表的操作。其实具体实现方式也差不多啦。

解题思路

根据题干我们知道，给定的两个链表是有序的。假设 l1 指向其中一个链表的头部， l2 指向另一个链表的头部，并初始化 head 和 current ，使它们指向一个默认的节点。我们比较 l1 指向节点的值 V(l1) 与 l2 指向节点的值 V(l2) 的大小，如果 V(l1) 的值小于 V(l2) 的值，则使 current.next 指向 l1 这个节点， current 指向下一个节点， l1 指向 l1的下一个节点 ，反之，则使 current.next 指向 l2 这个节点， current 指向下一个节点， l2 指向 l2的下一个节点 。

具体流程图如下：

注： l1 和 l2 存在有一个指向 空 时的处理方案是：将 current.next 指向不是空的的链表即可，因为给定的两个链表本身是有序的。

代码实现

GO语言实现

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    var (
        head = &ListNode{}
        current = head
    )

    for true {

        // l1 为空时，将 current.next 指向 l2 即可
        if l1 == nil {
            current.Next = l2
            break
        }

        // l2 为空时，将 current.next 指向 l1 即可
        if l2 == nil {
            current.Next = l1
            break
        }

        // 如果 l1的值 小于 l2的值 current.next指向l1，l1后移
        if l1.Val < l2.Val {
            current.Next = l1
            l1 = l1.Next
        } else {
            // 如果 l2的值 小于等于 l1的值 current.next指向l2，l2后移
            current.Next = l2
            l2 = l2.Next
        }

        // current 后移一位
        current = current.Next
    }
    
    // head 指向的是默认的节点，head.next 才是结果链表的头节点
    return head.Next

}

总结

欢迎关注我们的微信公众号，每天学习 Go 知识