Practice/Meta/Leetcode 445. Add Two Numbers II

Leetcode 445. Add Two Numbers II

CodingMust

Problem

You are given two linked lists representing two non-negative integers. The digits are stored in forward order, meaning the most significant digit is at the head of the list. Each node contains a single digit. Add the two numbers and return the sum as a linked list in the same forward order format.

You may assume the two numbers do not contain any leading zeros, except the number 0 itself.

Requirements

1. Return a new linked list representing the sum of the two input numbers
2. The result must maintain forward order (most significant digit first)
3. Handle carry propagation correctly across all digits
4. Support numbers of different lengths
5. Do not modify the input linked lists

Constraints

• The number of nodes in each linked list is in the range [1, 100]
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros
• Time complexity should be O(max(m, n)) where m and n are the lengths of the two lists
• Space complexity should be O(max(m, n)) for the result list

Examples

Example 1:

Input: l1 = [7, 2, 4, 3], l2 = [5, 6, 4] Output: [7, 8, 0, 7] Explanation: 7243 + 564 = 7807

Example 2:

Input: l1 = [2, 4, 3], l2 = [5, 6, 4] Output: [8, 0, 7] Explanation: 243 + 564 = 807

Example 3:

Input: l1 = [0], l2 = [0] Output: [0] Explanation: 0 + 0 = 0

Example 4:

Input: l1 = [9, 9, 9], l2 = [1] Output: [1, 0, 0, 0] Explanation: 999 + 1 = 1000 (carry creates a new digit)