Add Two Numbers (Linked Lists)

Difficulty: Hard · Topic: Linked lists

Two non-negative integers are stored as linked lists of single digits in reverse order (least-significant digit first). Given a and b, return their sum in the same format. Walk both lists together carrying the overflow — exactly like grade-school addition.

Examples

add_two_numbers([2,4,3], [5,6,4])
→ [7,0,8]

342 + 465 = 807.

add_two_numbers([0], [0])
→ [0]

Target complexity: time O(max(m, n)), space O(max(m, n))

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.