A non-negative integer is stored as a linked list of its decimal digits, least significant digit first: 125 is 5 -> 2 -> 1. Nodes are instances of the provided ListNode class. There are no leading zeros, so the last node is never 0, except for the number 0 itself, which is the single node 0.
Write add_lists(a, b) that returns the sum of the two numbers as a new list in the same format. Don't modify a or b.
In the examples, lists are written as Python lists, head first:
add_lists([8, 5], [7, 6]) # [5, 2, 1] (58 + 67 = 125)
add_lists([9, 9, 9], [1]) # [0, 0, 0, 1] (999 + 1 = 1000)
add_lists([0], [0]) # [0]
add_lists([3, 0, 2], [0]) # [3, 0, 2]
Constraints: each list has 1 to 200,000 nodes. Numbers this long don't fit in any machine integer (and Python refuses to convert strings of more than a few thousand digits to int by default), so work digit by digit. Aim for O(n + m) time.
Show hint
Add the way you would on paper, starting from the ones place, which is conveniently where both lists start. Keep going while either list has digits left or something is still being carried.