Use a dummy head to avoid special-casing the first node:
dummy = new ListNode(0)
tail = dummy
while list1 != null and list2 != null:
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 if list1 != null else list2
return dummy.next
At each step, compare the heads of both lists. Append the smaller one to the result and advance that list's pointer.
When one list is exhausted, append the remainder of the other list directly—no need to process node by node since it's already sorted.
Time: . Space: .