Merge Two Sorted Lists

Two linked lists are each sorted in non-decreasing order. Merge them into one sorted list by relinking their nodes.

List format. A linked list is given as two lines: its length n, then its n values from head to tail (the second line is empty when n = 0). When you print a list, print its values on one line separated by spaces, or the word empty if it has no nodes.

Input: two lists, one after the other (4 lines).

Output: the merged list.

Constraints: 0 ≤ n₁, n₂ ≤ 5·10⁴, −10⁵ ≤ value ≤ 10⁵.

Think about it: a dummy head node removes all the special cases for "which list starts the result". Keep a tail pointer and always attach the smaller front node.