Add Two Numbers

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list (also reverse-ordered).

Assume the two numbers do not contain any leading zero, except the number 0 itself.

Input / Output Format

Input: Heads of two linked lists l1 and l2. Output: Head of the linked list representing the sum.

Examples

Example 1

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

Example 2

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

Example 3

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1] Explanation: 9999999 + 9999 = 10009998.

Approach Hints

• Iterate both lists in parallel using a dummy head pointer.
• Track a carry variable. At each step: sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry. New node = sum % 10. carry = sum / 10.
• Continue while either list has nodes OR carry > 0.
• Time: O(max(m, n)). Space: O(max(m, n)) for output list.
• Common pitfall: forgetting to handle a trailing carry when both lists are exhausted.