0021. Merge Two Sorted Lists

題目

題目大意

解題思路

Big O

時間複雜 : O( log n) 空間複雜 : O(1)

來源

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

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0021.Merge-Two-Sorted-Lists/main.go

package mergetwosortedlists

type ListNode struct {
    Val  int
    Next *ListNode
}

// 時間複雜 O(log n), 空間複雜 O(1)
func MergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    head := &ListNode{Next: nil}
    cur := head

    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            cur.Next = list1
            list1 = list1.Next
        } else {
            cur.Next = list2
            list2 = list2.Next
        }
        cur = cur.Next
    }

    if list1 != nil {
        cur.Next = list1
    }
    if list2 != nil {
        cur.Next = list2
    }
    return head.Next
}

Benchmark