{x}
blog image

Add Two Numbers

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

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

 

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]

 

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.

Solution Explanation: Add Two Numbers

This problem involves adding two numbers represented as reversed linked lists. Each node in the list represents a digit, and the lists are arranged in reverse order (least significant digit first). The solution uses a simulation approach to mimic the process of manual addition.

Approach

  1. Initialization: A dummy node is created to simplify the handling of the result list's head. A carry variable is initialized to 0 to track any carry-over from previous additions.

  2. Iteration: The code iterates while either of the input lists (l1, l2) has remaining nodes or there's a carry-over (carry > 0).

  3. Summation: In each iteration:

    • The values of the current nodes in l1 and l2 (or 0 if a list is exhausted) are added along with the carry.
    • The divmod (or equivalent modulo and integer division) operation calculates the new carry (the quotient) and the current digit's value (the remainder).
    • A new node with the calculated digit's value is appended to the result list.

  4. List Traversal: The pointers l1 and l2 are advanced to the next nodes in their respective lists.

  5. Return Value: After the loop completes, the dummy node's next pointer points to the head of the result list, which is returned.

Time and Space Complexity

  • Time Complexity: O(max(m, n)), where 'm' and 'n' are the lengths of the input linked lists. The algorithm iterates through the lists once, performing constant-time operations in each iteration.

  • Space Complexity: O(max(m, n)). The space is primarily used to store the resultant linked list, whose length is at most max(m, n) + 1 (to accommodate a potential extra carry digit). Ignoring the space used by the result list, the auxiliary space used is O(1).

Code Examples (Python, Java, C++, Go, TypeScript, Rust, JavaScript, C#, PHP, Swift, Ruby and Nim)

The provided code in various programming languages implements this simulation approach. All versions share the same core logic; only syntax and standard library functions differ. The examples are well commented and should be easy to understand. Note that the ListNode structure varies slightly in implementation depending on the language. Each language includes its own implementation of this data structure.

Example Walkthrough (Python)

Let's trace the Python code with l1 = [2, 4, 3] and l2 = [5, 6, 4]:

  1. Initialization: dummy node is created, carry = 0.
  2. Iteration 1: s = 3 + 4 + 0 = 7. carry = 0, val = 7. A node with val = 7 is added to the result list.
  3. Iteration 2: s = 4 + 6 + 0 = 10. carry = 1, val = 0. A node with val = 0 is added.
  4. Iteration 3: s = 2 + 5 + 1 = 8. carry = 0, val = 8. A node with val = 8 is added.
  5. Loop Termination: l1, l2, and carry are all 0, so the loop ends.
  6. Return: The result list [7, 0, 8] is returned.

This mirrors the manual addition process: 342 + 465 = 807 (reversed in the linked list representation).