360. Add Two Numbers II
Two non-negative integers arrive as singly linked lists l1 and l2, one decimal digit per node, most significant digit first — so 7 → 2 → 4 → 3 is the number 7243. Neither list has leading zeros, except when the number itself is 0.
Return the head of a new linked list holding their sum, in the same most-significant-first orientation and with no leading zeros.
The forward orientation is what makes this harder than the classic reverse-order version: addition wants to start at the ones digit, but the list hands you the biggest digit first. Follow-up: can you do it without reversing either input list?
Example 1:
Input: l1 = [7, 2, 4, 3], l2 = [5, 6, 4]
Output: [7, 8, 0, 7]
Explanation: The lists encode 7243 and 564. Their sum is 7807, which reads front-to-back as 7 → 8 → 0 → 7.
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 — the one case where a result may (and must) be the single digit 0.
Constraints:
- 1 ≤ number of nodes in each list ≤ 100
- 0 ≤ node value ≤ 9
- Neither input has leading zeros, except the number 0 represented as the single node [0].
Hints:
If the digits were least-significant first this would be the classic carry-propagation add. Can you get them into that order — or simulate that order?
A stack reverses order for free: push every digit, then pop to consume both numbers ones-digit first.
Build the result front-first while adding: create each new digit node and hook it *in front of* the nodes built so far, so no final reversal is needed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: l1 = [7, 2, 4, 3], l2 = [5, 6, 4]
Expected output: [7, 8, 0, 7]