leetcode-合并两个有序链表

题目
将两个升序链表合并为一个新的升序链表并返回。

示例：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

分析
比较大小
那必须两个链表都要遍历，无论从哪个链表开始遍历，都不影响，假设我们从l1开始遍历，取出第一个数比较，只有两种情况，小于等于或大于，那么意味着我们这一轮比较我们获得了其中的较小值。
那么这个最小值是否是我们目标的链表的最小值呢？
答案，是的！假设l1第一个数v1比另一个链表l2的第一个值v2小，那必然比l2整个链表小，因为链表是升序的，同时v1也是l1中最小的值，那问题就比较简单了，我们只需要取出这个最小节点，放到一个新节点末尾，那么不就可以得到我们的目标链表了吗？于是就有以下实现：

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
        // 定义目标链表
    var l3 = &ListNode{0, nil}
        // 由于新节点需要放到链表末尾，所以在这个过程中我们需要更新目标链表尾节点。
    tail := l3
    // 当其中一个链表为空时结束
    for l1 != nil && l2 != nil {
        v1 := l1.Val
        v2 := l2.Val
                // 每一轮，总是将最小的值放到l3末尾,同时剔除该节点
        if v1 <= v2 {
            tail.Next = &ListNode{v1, nil}

            p := l1.Next
            l1 = p
        } else {
            tail.Next = &ListNode{v2, nil}

            p := l2.Next
            l2 = p
        }

        tail = tail.Next
    }
    return l3.Next
}

提交测试，

1/208 cases passed (N/A)
Testcase
[1,2,4]
[1,3,4]
Answer
[1,1,2,3,4]
Expected Answer
[1,1,2,3,4,4]

不通过，仔细查看，原来是漏掉了节点。
再查看代码，由于剔除节点后，链表长度会不一致，那整个遍历会导致其中一个链表先为空，那么至于是哪个链表为空，我们无需关心，只需要将不为空的链表放到目标链表末尾即可。完整实现如下：

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
        // 定义目标链表(哑节点)
    var l3 = &ListNode{0, nil}
        // 由于新节点需要放到链表末尾，所以在这个过程中我们需要更新目标链表尾节点。
    tail := l3
    // 当其中一个链表为空时结束
    for l1 != nil && l2 != nil {
        v1 := l1.Val
        v2 := l2.Val
                // 每一轮，总是将最小的值放到l3末尾,同时剔除该节点
        if v1 <= v2 {
            tail.Next = &ListNode{v1, nil}

            p := l1.Next
            l1 = p
        } else {
            tail.Next = &ListNode{v2, nil}

            p := l2.Next
            l2 = p
        }

        tail = tail.Next
    }
        // 将不为空的链表放到目标链表末尾
        if l1 != nil {
        tail.Next = l1
    }
    if l2 != nil {
        tail.Next = l2
    }
    return l3.Next
}

提交测试，完美通过。

208/208 cases passed (0 ms)
Your runtime beats 100 % of golang submissions
Your memory usage beats 10.18 % of golang submissions (2.6 MB)