You are given two non empty singly linked lists l1 and l2 that represent two non negative integers. Each node stores a single digit in Node.val, and the digits are ordered from most significant to least significant.

Return the sum of the two numbers as a singly linked list in the same most significant to least significant digit order.

Note: Follow up: can you solve this without reversing the input lists?

Constraints:

• The number of nodes in each of l1 and l2 is in the range $[1, 100]$.

• $0 \leq$ Node.val $\leq 9$.

• Each list represents a number with no leading zeros.

Input: l1 = [9,9,9]-ListNode, l2 = [1]-ListNode
Output: [1,0,0,0]-ListNode
Explanation: Adding from the least significant digits using stacks gives 999 + 1 = 1000. The carry propagates through all digits, producing a new leading 1.

Input: l1 = [1,0,0,0]-ListNode, l2 = [9,9,9]-ListNode
Output: [1,9,9,9]-ListNode
Explanation: 1000 + 999 = 1999. Only the last three positions require carry handling, and the most significant 1 remains.

Input: l1 = [8,7,6,5,4,3,2,1]-ListNode, l2 = [1,2,3,4,5,6,7,9]-ListNode
Output: [1,0,0,0,0,0,0,0,0]-ListNode
Explanation: 87654321 + 12345679 = 100000000. Every digit pair sums to 10 with carry, resulting in all zeros and a new leading 1.

Input: l1 = [5]-ListNode, l2 = [5]-ListNode
Output: [1,0]-ListNode
Explanation: 5 + 5 = 10, and the resulting carry becomes a new most significant digit.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.