You are given l1 and l2, two non-empty linked lists that each hold a non-negative integer,
one decimal digit per node, with the ones digit first. So [3, 0, 8] is the number 803.
Return the sum of the two numbers as a linked list in the same form. Neither number has leading
zeros, except the number 0 itself, which is [0], and the sum mustn't have any either.
The numbers can have up to 100 digits, far more than an ordinary integer holds, so add them digit by digit.
Example 1
- Input
- l1 = [3, 0, 8], l2 = [9, 4]
- Output
- [2, 5, 8]
Example 2
- Input
- l1 = [9, 9], l2 = [1]
- Output
- [0, 0, 1]
Constraints
- Each list holds 1 to 100 nodes.
- Every node holds a digit from 0 to 9.
- No list ends in a 0, except the list
[0].
Show the pattern
Linked list
The digits arrive ones digit first, the order you add them by hand, so you walk both lists in step, carrying as you go, and build the answer node by node behind a dummy head.
See linked list in a visualiserShow the approach
Walk both lists at once with a running carry, starting at 0. In each column, add the two
digits (0 for a list that has already ended) and the carry. The new node holds total % 10, and
the carry becomes total // 10. Append each new node behind a dummy head.
Keep going while either list has nodes left or the carry is 1, so a final carry becomes a node of
its own. The sum starts at dummy.next.
Time: O(max(m, n)) · Space: O(max(m, n)) for the answer