Scale Engineer

Add Two Numbers

Med
#0002Time: O(max(N, M))Space: O(max(N, M))35 companies
Patterns
MathRecursion
Data structures
Linked List
Companies
AccentureAdobeAirbnbAmazon

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves converting the two linked lists into their corresponding integer representations. After converting, we add these two numbers together. Finally, the resulting sum is converted back into a linked list in the required reverse-digit format.

Algorithm

  • Create a helper function listToBigInt that converts a linked list to a BigInteger.
  • Inside listToBigInt, iterate through the list, building a string representation of the number by prepending each digit. This correctly reverses the list order.
  • Convert the final string to a BigInteger.
  • In the main function, call listToBigInt for both l1 and l2.
  • Use the add method of BigInteger to compute the sum.
  • Convert the resulting BigInteger sum back to a string.
  • Create a dummyHead for the result list.
  • Iterate through the sum string from right to left (end to start).
  • For each character, parse the digit, create a new ListNode, and append it to the result list.
  • Return dummyHead.next. Handle the edge case where the sum is 0.

Walkthrough

The core idea is to transform the linked list representation of numbers into a standard numerical type that the computer can perform arithmetic on directly.

  1. Convert Linked Lists to Numbers: We traverse each linked list, l1 and l2. Since the digits are in reverse order, we can build the number by effectively multiplying each digit by its corresponding power of 10. A crucial point is that the numbers can be very large, exceeding the capacity of standard 64-bit integers (long in Java). Therefore, we must use a class designed for arbitrary-precision arithmetic, like java.math.BigInteger.

  2. Sum the Numbers: Once we have the two numbers as BigInteger objects, we simply use the add method to compute their sum.

  3. Convert Sum back to Linked List: We convert the BigInteger sum back to a string. We then iterate through this string in reverse to create the new linked list, as the problem requires digits in reverse order. Each character is converted to a digit and placed in a new ListNode.

import java.math.BigInteger; /** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        // Step 1: Convert linked lists to BigInteger        BigInteger num1 = listToBigInt(l1);        BigInteger num2 = listToBigInt(l2);         // Step 2: Add the numbers        BigInteger sum = num1.add(num2);         // Step 3: Convert sum back to a linked list        String sumStr = sum.toString();        ListNode dummyHead = new ListNode(0);        ListNode current = dummyHead;                // Handle the case of sum being 0        if (sum.equals(BigInteger.ZERO)) {            return new ListNode(0);        }         for (int i = sumStr.length() - 1; i >= 0; i--) {            int digit = sumStr.charAt(i) - '0';            current.next = new ListNode(digit);            current = current.next;        }                return dummyHead.next;    }     private BigInteger listToBigInt(ListNode node) {        StringBuilder sb = new StringBuilder();        while (node != null) {            sb.insert(0, node.val);            node = node.next;        }        return new BigInteger(sb.toString());    }}

Complexity

Time

O(max(N, M))

Space

O(max(N, M))

Trade-offs

Pros

  • Conceptually simple to understand if the BigInteger class is familiar.

  • Leverages powerful, built-in arithmetic capabilities.

Cons

  • Suffers from integer overflow if standard integer types like long are used. Requires a special class like BigInteger.

  • Less efficient due to the overhead of converting between data structures (list to string, string to BigInteger, BigInteger back to string, and string back to list).

  • This approach might be considered less fundamental as it abstracts away the core logic of addition into a library function.

Solutions

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode AddTwoNumbers ( ListNode l1 , ListNode l2 ) { ListNode dummy = new ListNode (); int carry = 0 ; ListNode cur = dummy ; while ( l1 != null || l2 != null || carry != 0 ) { int s = ( l1 == null ? 0 : l1 . val ) + ( l2 == null ? 0 : l2 . val ) + carry ; carry = s / 10 ; cur . next = new ListNode ( s % 10 ); cur = cur . next ; l1 = l1 == null ? null : l1 . next ; l2 = l2 == null ? null : l2 . next ; } return dummy . next ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem