Practice/Amazon/Leetcode 2. Add Two Numbers

Leetcode 2. Add Two Numbers

CodingMust

Problem

You are given the heads of two sorted singly linked lists. Each list is sorted in ascending order. Your task is to merge these two lists into a single sorted linked list and return the head of the merged list.

The merged list should be constructed by splicing together the nodes from the two input lists. You should not create new nodes; instead, rearrange the existing nodes to form the merged result.

Requirements

1. Merge two sorted linked lists into one sorted linked list
2. The resulting list must maintain sorted order (ascending)
3. Use the existing nodes from both input lists without creating new nodes
4. Return the head of the merged linked list

Constraints

• The number of nodes in both lists is in the range [0, 50]
• -100 ≤ Node.val ≤ 100
• Both list1 and list2 are sorted in ascending order

Examples

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4] Explanation: We merge the nodes alternating between lists based on their values to maintain sorted order

Example 2:

Input: list1 = [], list2 = [0] Output: [0] Explanation: The first list is empty, so we simply return the second list

Example 3:

Input: list1 = [], list2 = [] Output: [] Explanation: Both lists are empty, so the result is an empty list

Example 4:

Input: list1 = [1,3,5], list2 = [2,4,6,8,10] Output: [1,2,3,4,5,6,8,10] Explanation: We interleave nodes from both lists while maintaining sorted order