309. Merge Two Sorted Linked Lists

Given the heads of two sorted singly linked lists list1 and list2, merge them into one sorted list. The merged list should be made by splicing together the nodes of the first two lists.

Return the head of the merged sorted list.

Input: Heads of two sorted singly linked lists list1 and list2.

Output: Head of the merged sorted linked list.

Examples

Input: [1,2,4], [1,3,4]
Output: [1,1,2,3,4,4]
Explanation: Use dummy head. Compare 1 vs 1 → take list1(1). Compare 2 vs 1 → take list2(1). Compare 2 vs 3 → take list1(2). Compare 4 vs 3 → take list2(3). Compare 4 vs 4 → take list1(4). Append list2(4). Result: 1→1→2→3→4→4.

Input: [], []
Output: []
Explanation: Both lists empty. Return NULL.

Input: [], [0]
Output: [0]
Explanation: First list is empty. Return list2 head = node(0).

Constraints

• 0 <= number of nodes in each list <= 50
• -100 <= Node.val <= 100
• Both lists are sorted in non-decreasing order

Asked by