Add Two Numbers

You are given two non-empty linked lists, l1 and l2, each representing a non-negative integer. The digits are stored in reverse order — meaning the head of each list holds the least significant digit — and each node holds a single digit from 0 to 9.

Add the two numbers together and return the sum as a new linked list, again with digits stored in reverse order (least significant digit first).

Rules to keep in mind:

• Neither input list contains leading zeros in its represented number, except when the number itself is exactly 0 (in which case the list is a single node holding 0).
• The two lists may have different lengths.
• Assume you cannot convert the lists into big integers directly, or use any built-in arbitrary-precision arithmetic shortcuts — the intended approach walks the lists node by node, carrying over any overflow past 9 into the next digit position, similar to how you'd add numbers by hand on paper.
• Do not mutate the input lists if you don't have to — return a freshly built list for the result.

Examples

Example 1:

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

Output: [7,0,8]

Explanation:

• l1 represents the number 243 (reading digits from tail to head, since the list stores them least-significant first: 3,4,2 → 243).
• l2 represents 564.
• 243 + 564 = 807, which reversed into linked-list digit order is [7,0,8].

Example 2:

Input: l1 = [9,9], l2 = [1]

Output: [0,0,1]

Explanation:

• l1 represents 99, l2 represents 1.
• 99 + 1 = 100, so the result digits in reverse order are [0,0,1].
• This case shows a carry propagating all the way past the end of the longer list, producing an extra digit in the output.

Example 3:

Input: l1 = [0], l2 = [0]

Output: [0]

Explanation:

• Both lists represent the number 0, so the sum is 0, represented as a single-node list [0].

Constraints

• The number of nodes in each list is between 1 and 100, inclusive.
• Each node's value is a digit between 0 and 9, inclusive.
• Neither list represents a number with a leading zero, unless that number is 0 itself.