【LeetCode】21. 合并两个有序链表

---

一、题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

原题链接：

---

二、我的题解

解题思路

1. 创建第三个新的链表 head ，它的 head 首先指向头比较小的那个链表，然后不断更新新链表的 Next 域来完成合并;
2. 新链表的尾 tail 初始化为它的 head ；
3. 不断比较 list1 和 list2 当前的 Val ，比较小的作为新表 tail 的 Next ；
4. 直到 list1 和 list2 的其中一个表结束啦，就把另一个表剩下的部分续在新表的 tail 上就行啦；
5. 返回 head 。

Go 语言代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil && list2 == nil{
        return nil
    }
    if list1 == nil{
        return list2
    }
    if list2 == nil{
        return list1
    }
    
    var head,tail *ListNode
    // 找头
    if list1.Val <= list2.Val{
       head = list1
       list1 = list1.Next
    }else{
       head = list2
       list2 = list2.Next
    }
    
    tail = head
    for list1 != nil && list2 != nil{
        if list1.Val <= list2.Val{
            tail.Next = list1
            tail = tail.Next
            list1 = list1.Next
        }else{
            tail.Next = list2
            tail = tail.Next
            list2 = list2.Next
        }
    }

    if list1 == nil && list2 == nil{
        return head
    }else if list1 == nil{
        tail.Next = list2
        return head
    }else{
        tail.Next = list1
        return head
    }

}

评判结果：