add-two-numbers.sh — zsh
← listnormal view →

Add Two Numbers

medium
PreviousNext
linked-listmathsimulation

You are given two non-empty linked lists, l1 and l2, 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, in the same reversed-digit form.

You may assume neither number has a leading zero, except the number 0 itself.

Input / output

  • Input: l1: ListNode, l2: ListNode (JSON test fixtures are plain arrays of digits, least-significant digit first, e.g. [2, 4, 3] means the number 342)
  • Output: ListNode — the sum, digits in the same reversed order (serialized the same way)

Constraints

  • The number of nodes in each list is between 1 and 100.
  • 0 <= node value <= 9
  • Neither number has a leading zero, unless the number itself is 0.

Follow-up

Can you do this in a single pass with O(1) extra space beyond the output list, without ever converting either list to an integer (which would fail for arbitrarily large numbers)?

Examples
Example 1
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Example 2 (both zero)
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3 (carry cascades through the longer list)
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
🔒 6 hidden
Running will execute all 9 cases, including 6 hidden ones.