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