21. 合并两个有序链表

发表于： 分类于：
字数： 260 阅读：≈ 1分钟 浏览：

https://leetcode.cn/problems/merge-two-sorted-lists/

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

示例 1： 

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

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

代码 

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    }
    if list2 == nil {
        return list1
    }
    n1, n2 := list1, list2
    target := &ListNode{}
    h := target
    for n1 != nil || n2 != nil {
        // n1, n2 其中一个链表用完后，另一个链表直接加入结果
        if n1 == nil {
            target.Next = n2
            break
        }
        if n2 == nil {
            target.Next = n1
            break
        }
        // n1,n2 比较，把小的加入结果，并移动链表
        if n1.Val <= n2.Val {
            target.Next = &ListNode{
                Val: n1.Val,
            }
            n1 = n1.Next
            target = target.Next
        } else {
            target.Next = &ListNode{
                Val: n2.Val,
            }
            n2 = n2.Next
            target = target.Next
        }

    }
    return h.Next
}