package LinkedList
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
virtualHead := new(ListNode)
tail := virtualHead
cur1, cur2 := list1, list2
for cur1 != nil && cur2 != nil {
if cur1.Val <= cur2.Val {
tail.Next = cur1
tail = tail.Next
cur1 = cur1.Next
} else {
tail.Next = cur2
tail = tail.Next
cur2 = cur2.Next
}
}
for cur1 != nil {
tail.Next = cur1
tail = tail.Next
cur1 = cur1.Next
}
for cur2 != nil {
tail.Next = cur2
tail = tail.Next
cur2 = cur2.Next
}
return virtualHead.Next
}