021-合并两个有序链表

Description

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

Example
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
Solution
type ListNode struct {
    Val int
     Next *ListNode
}


func formatList2Node(list []int)*ListNode  {
    head := new(ListNode)
    current := head
    for i := range list{
        current.Next = new(ListNode)
        current.Next.Val = list[i]
        current = current.Next
    }
    return head.Next
}


//遍历
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    head := new(ListNode)
    current := head
    for l1 != nil || l2 != nil {
        if l1 == nil {
            current.Next = l2
            break
        }
        if l2 == nil {
            current.Next = l1
            break
        }
        if  l1.Val < l2.Val {
            current.Next = l1
            l1 = l1.Next
        }else {
            current.Next = l2
            l2 = l2.Next
        }
        current = current.Next
    }
    return head.Next
}


//递归
func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    result := new(ListNode)
    if l1.Val > l2.Val {
        result = l2
        result.Next = mergeTwoLists(l1,l2.Next)
    }else {
        result = l1
        result.Next = mergeTwoLists(l1.Next,l2)
    }
    return result
}

leetCode地址