Problem Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

2.jpg

  • Input: l1 = [2,4,3], l2 = [5,6,4]
  • Output: [7,0,8]

Example 2:

  • Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  • Output: [8,9,9,9,0,0,0,1]

My Idea

The idea here was to store the result in a new list res. The addition process continues until both l1and l2 have been used up and there is no more carry-over from previous additions. At each step we calculate the sum and respective carry-over and move to the next nodes. This yields a time complexity of O(max(n,m))

My solution

from typing import Optional
#Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Time Complexity: O(max(n,m))
def addTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    if not l1:
        return l2
    if not l2:
        return l1

    res = ListNode(0)
    curr = res
    carry = 0

    while l1 or l2 or carry:
        a1 = l1.val if l1 else 0
        a2 = l2.val if l2 else 0

        total = a1 + a2 + carry
        carry = total // 10
        curr.next=ListNode(total%10)
        curr = curr.next
        if l1:
            l1=l1.next
        if l2:
            l2=l2.next
    return res.next