Add Two Numbers
Medium· dummy head· simulation
Problem
Two non-negative integers are stored as linked lists with their digits in reverse order, one digit per node. Return their sum in the same reversed-digit list format.
Examples
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
342 + 465 = 807.
Input: l1 = [9,9], l2 = [1]
Output: [0,0,1]
99 + 1 = 100; the carry creates a new node.
Constraints
- • 1 <= nodes in each list <= 100
- • 0 <= Node.val <= 9
- • No leading zeros except the number 0
Hints & approach
Hint 1
Reverse order means the head is the ones digit, so you can add left to right like on paper.
Hint 2
Keep a carry, and continue while either list or the carry is non-zero.
Approachtry the hints first
Walk both lists together with a carry starting at 0. At each step add the current digits (0 if a list is exhausted) plus the carry, append a node holding sum % 10, and set carry = sum / 10. Keep looping while either list has nodes left or carry is non-zero so a final carry produces an extra digit. A dummy head keeps the append logic uniform.
Time O(max(n, m)) · Space O(max(n, m)) for the output