Merge Two Sorted Lists

Problem

You are given the heads of two singly linked lists, each already sorted in non-decreasing order. Splice the nodes of the two lists together into a single sorted list and return its head. Reuse the existing nodes; do not create new ones.

• Each list has between 0 and 200 nodes.
• Node values fit in a signed 32-bit integer.
• Both lists are sorted in non-decreasing order.

Examples

• l1 = 2 -> 5 -> 9, l2 = 3 -> 5 -> 11 → 2 -> 3 -> 5 -> 5 -> 9 -> 11. Equal values from both lists are both kept.
• l1 = empty, l2 = empty → empty.
• l1 = 7, l2 = empty → 7. When one list is empty the other is already the answer.

Hints

1. At each step, which of the two current heads must come next in the merged list?
2. Building a list by appending requires a pointer to the current tail. What do you attach the very first node to?
3. Use a dummy head node so the tail pointer always has something to append to, then attach whichever list is left over.