21. Merge Two Sorted Lists

Easy

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output:
 [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output:
 []

Example 3:

Input: list1 = [], list2 = [0]
Output:
 [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].

• -100 <= Node.val <= 100

• Both list1 and list2 are sorted in non-decreasing order.

解題

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    cur1 := list1
    cur2 := list2
    head := &ListNode{}
    cur := head

    for cur1 != nil || cur2 != nil {
        if cur1 == nil {
            cur.Next = cur2
            cur = cur.Next
            cur2 = cur2.Next
        } else if cur2 == nil {
            cur.Next = cur1
            cur = cur.Next
            cur1 = cur1.Next
        } else {
            if cur1.Val <= cur2.Val {
                cur.Next = cur1
                cur = cur.Next
                cur1 = cur1.Next
            } else {
                cur.Next = cur2
                cur = cur.Next
                cur2 = cur2.Next
            }
        }
    }

    return head.Next
}