You're given the heads of two sorted linked lists, list1 and list2. Merge them into one sorted list by splicing their nodes together, and return its head.
Lists are written as arrays: [1, 2, 4] means 1 → 2 → 4.
Examples
Example 1
- Input
- list1 = [1, 2, 4], list2 = [1, 3, 4]
- Output
- [1, 1, 2, 3, 4, 4]
Example 2
- Input
- list1 = [], list2 = []
- Output
- []
Example 3
- Input
- list1 = [], list2 = [0]
- Output
- [0]
Constraints
- Each list has between
0and50nodes. -100 <= Node.val <= 100- Both lists are sorted in non-decreasing order.