Add two numbers represented by linked lists
Filed under Amazon · Also reported at ADP, Arista Networks, Azuga Telematics, Bloomberg, DocuSign, General Mills, Goldman Sachs, Kuliza and 11 more
Free read 1 of 3Confirm digit order, lists of different lengths, no leading zeros except for the number 0, and whether input lists may be modified.
The question
Two non-negative integers are stored as linked lists with one digit per node, least significant digit first. Add them and return the sum as a linked list in the same form. If the digits were stored most significant first, the same idea applies after reversing the lists.
Constraints
- Each list has 1 to 100 nodes
- Each node holds a digit 0-9
- No leading zeros except the number 0 itself
Examples
- Input
- [2,4,3] + [5,6,4]
- Output
- [7,0,8]
- Why
- 342 + 465 = 807, stored reversed.
- Input
- [9,9] + [1]
- Output
- [0,0,1]
- Why
- 99 + 1 = 100, so the final carry creates a new node.
Approach
Confirm digit order, lists of different lengths, no leading zeros except for the number 0, and whether input lists may be modified.
Convert each list to an integer, add and convert back. It works in Python but overflows in languages with fixed-size integers and defeats the purpose.
Walk both lists together, adding digits plus carry; create a node for sum % 10 and carry = sum // 10. Continue while either list or carry remains. Use a dummy head node to simplify appending.
Different lengths, a final carry creating an extra node (for example 5 + 5 = 10), and lists holding 0. Time O(max(m, n)), space O(1) beyond the output.
Solution
O(max(m, n)) time, O(1) extra space
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def build(a):
head = cur = ListNode()
for x in a:
cur.next = ListNode(x); cur = cur.next
return head.next
def to_list(node):
out = []
while node:
out.append(node.val); node = node.next
return out
class Solution:
def addTwoNumbers(self, l1, l2):
dummy = cur = ListNode()
carry = 0
while l1 or l2 or carry:
s = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0)
carry, digit = divmod(s, 10)
cur.next = ListNode(digit); cur = cur.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
Tips
- What they are testing: Pointer handling, carry propagation and use of a dummy head to avoid special cases.
- Common mistake: Dropping the final carry or stopping when the shorter list ends.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.