Add Two Numbers II

Explanation & Solution

Description

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may not modify the input lists. In other words, reversing the lists is not allowed.

Input:l1 = [7,2,4,3], l2 = [5,6,4]

Output:[7,8,0,7]

Explanation: 7243 + 564 = 7807.

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 (except the number 0 itself)

Approach

Fast and Slow Pointers pattern

1. Set Up Pointers and Carry

Initialize pointer i at the last index of l1 and pointer j at the last index of l2
Initialize carry to 0
Create an empty result array to build the answer

2. Process Digits from Right to Left

Loop while i >= 0 or j >= 0 or carry > 0
At each step, compute sum = digit from l1[i] (or 0 if exhausted) + digit from l2[j] (or 0 if exhausted) + carry
Compute the new carry: carry = Math.floor(sum / 10)
Prepend the current digit sum % 10 to the front of result using unshift
Decrement i and j after reading each digit

3. Return the Result

When the loop ends, result contains all digits of the sum from most significant to least significant
Return result

4. Why This Works (Stack Intuition)

Instead of using explicit stacks, we use array indices to traverse from right to left
This simulates popping from two stacks simultaneously
The carry propagation naturally handles cases where the sum produces an extra leading digit (e.g., 999 + 1 = 1000)

🧠 Key Insight

The key challenge is that digits are stored most-significant-first, but addition must proceed from least-significant digits
Using indices from the end of each array avoids the need to reverse the lists

Time

**O(max(m, n))** where m and n are the lengths of the two lists

Space

**O(max(m, n))** for the result array

Solution Code

Swap Nodes in Pairs

Flatten a Multilevel Doubly Linked List