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
}
​