Add Two Numbers

Add Two Numbers is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the Addition of Numbers subpattern.

Problem statement

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.

Topics and companies

Topics: Linked List, Math, Recursion.

Reported in interviews at Bloomberg, Microsoft, Amazon, Google, Facebook, Apple, Adobe, Paypal, Coupang, Oracle, Uber, VMware and others.

How to practise Add Two Numbers on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Add Two Numbers in the code editor, or read the Add Two Numbers editorial for a worked solution with its approach and complexity analysis.

Where Add Two Numbers sits in the DSA pattern sheet

• Linked List Manipulation Patterns pattern guide
• Addition of Numbers subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Add Two Numbers

Other problems that use the same Addition of Numbers and Linked List Manipulation Patterns techniques:

• Plus One Linked List — Medium, same subpattern
• Intersection of Two Linked Lists — Easy, same pattern
• Merge Two Sorted Lists — Easy, same pattern
• Minimum Index Sum of Two Lists — Easy, same pattern
• Odd Even Linked List — Medium, same pattern
• Palindrome Linked List — Easy, same pattern