剑指 25. 合并两个排序的链表

剑指 Offer 25. 合并两个排序的链表

//迭代法 哨兵模式,复杂度On,O1
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    prev := dummy
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            prev.Next = l1
            l1 = l1.Next
        } else {
            prev.Next = l2
            l2 = l2.Next
        }
        prev = prev.Next
    }
    if l1 == nil {
        prev.Next = l2
    }
    if l2 == nil {
        prev.Next = l1
    }
    return dummy.Next
}

//递归法 通法，复杂度On,On
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }

    var res *ListNode
    if l1.Val <= l2.Val {
        res = l1
        res.Next = mergeTwoLists(l1.Next, l2)
    } else {
        res = l2
        res.Next = mergeTwoLists(l2.Next, l1)
    }
    return res
}