aloalgoMerge Two Sorted Lists
Easy
You are given the heads of two linked lists, l1 and l2.
Your task is to merge these two lists into one sorted list.
You may assume that:
- The input linked lists,
l1andl2, are already sorted in non-decreasing order.
Return the head node of the new merged list.
Example 1
Inputs
l1 = 1 → 3 → 5 → null
l2 = 2 → 4 → 6 → 7 → 8 → null
Output
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → null
Explanation:
The two lists are merged in sorted order.
Example 2
Inputs
l1 = 1 → 2 → 4 → null
l2 = 1 → 3 → 4 → null
Output
1 → 1 → 2 → 3 → 4 → 4 → null
Explanation:
The two lists are merged in sorted order, including duplicates.
Example 3
Inputs
l1 = None
l2 = None
Output
None
Explanation:
Merging two empty lists results in an empty list.
Example 4
Inputs
l1 = None
l2 = 0 → 3 → 5 → null
Output
0 → 3 → 5 → null
Explanation:
Merging an empty list with a non-empty list results in the non-empty list.
Example 5
Inputs
l1 = 2 → 6 → 8 → null
l2 = 1 → 3 → 7 → 9 → null
Output
1 → 2 → 3 → 6 → 7 → 8 → 9 → null
Explanation:
Nodes are merged in order to maintain sorting.
Inputs
l1 = 1 → 3 → 5 → null
l2 = 2 → 4 → 6 → 7 → 8 → null
Output
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → null