Add Two Numbers

The problem

You are given two non-empty linked lists representing two non-negative integers. Add the two numbers and return as a linked list.

Function: def addTwoNumbers(l1,l2):

Example input (a JSON list of arguments): [[2, 4, 3], [5, 6, 4]]
Expected output: [7, 0, 8]

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Digits are stored least-significant first.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def addTwoNumbers(l1,l2):
    head=tail=ListNode(); carry=0
    while l1 or l2 or carry:
        value=carry
        if l1: value+=l1.val; l1=l1.next
        if l2: value+=l2.val; l2=l2.next
        carry,digit=divmod(value,10); tail.next=ListNode(digit); tail=tail.next
    return head.next

Why it works

Digits are stored least-significant first. Add matching digits plus carry and allocate a result node for each output digit, including a final carry after both lists finish.

Complexity: O(max(m,n)) time / O(max(m,n)) result space.

Time: O(max(m,n)) time · Space: O(max(m,n)) result space