Merge Two Sorted Lists

You're given the starting nodes (heads) of two linked lists, list1 and list2. Both are already sorted in increasing order.

Combine them into a single sorted linked list. Instead of creating brand-new nodes, reuse the existing nodes from the two lists and just relink them in the right order.

Return the head of this new combined list.

Example 1:

Input:  list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input:  list1 = [], list2 = []
Output: []

Constraints:

• Each list can have anywhere from 0 to 50 nodes.
• Every node's value is between -100 and 100.
• Both lists are already sorted from smallest to largest (values may repeat).