Write merge_two_lists(a, b): both arguments are heads of linked lists (ListNode, possibly None) sorted in non-decreasing order. Return the head of one sorted list that contains every node of both.
Splice the existing nodes together; don't allocate new value nodes (a dummy/sentinel node for convenience is fine, as long as it isn't in the result). Each list has up to 100,000 nodes and the values fit in 32-bit integers. Work iteratively, since the lists can be long, and aim for O(n + m) time.
a: 2 -> 4 -> 8 b: 1 -> 4 -> 5 -> 9
result: 1 -> 2 -> 4 -> 4 -> 5 -> 8 -> 9
a: (empty) b: 3
result: 3