You get list1 and list2, the heads of two sorted linked lists.
Merge them into one sorted list, and return its head.
Use the nodes you already have. Change their next links to form one chain, and don't make new nodes.
Either list can be empty (its head is NULL). Both can be empty too.
Example 1:
Input: list1 = [2,6,7], list2 = [3,6,10,11] Output: [2,3,6,6,7,10,11] Explanation: Both lists have a 6. The 6 from list1 goes first. After the 7, list1 has no nodes left. The rest of list2, 10 -> 11, goes at the end as it is.
Example 2:
Input: list1 = [5,9], list2 = [] Output: [5,9] Explanation: The second list is empty. So the answer is list1, unchanged.
Example 3:
Input: list1 = [-8,-1], list2 = [-5,4,4] Output: [-8,-5,-1,4,4] Explanation: Negative values and repeats work the same way. The result is -8, -5, -1, then 4 -> 4.
Constraints:
- Each list has 0 to 10,000 nodes.
- Each value is from -100,000 to 100,000.
- Both lists are in ascending order.
- A value can repeat.
Note:
Your algorithm should run in O(n + m) time and use O(1) extra space, where n and m are the lengths of list1 and list2: it only re-links the nodes that are already there.
Start the merged list with a dummy node, an extra node before the first real node. Then the first node needs no special case. Every node is attached after the merged list's last node in the same way. The answer is the node after the dummy.
Merge the lists in a loop. A recursive merge goes one call deeper for every node. With 2 × 104 nodes, it can run out of call stack.
Free plan: 30 tutor messages. PRO is unlimited.
