Problem Statement in English

You’re 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.

Approach

We can solve this problem by first parsing the two linked lists into integers, adding them together, and then converting the result back into a linked list.

And we’re done!

Solution in Python


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def parse(head):
            count = 0
            num = 0

            while head:
                v = head.val
                v *= 10**count
                num += v
                count += 1
                head = head.next
            
            return num

        n1 = parse(l1)
        n2 = parse(l2)

        res = n1 + n2
        if not res:
            return ListNode(0)

        head = ListNode()
        temp = head
        while res:
            temp.next = ListNode(res % 10)
            temp = temp.next
            res //= 10
        
        return head.next

Complexity

  • Time: $O(m + n)$
    Since we need to iterate over both linked lists to parse them into integers.

  • Space: $O(m + n)$
    Since we create a new linked list to store the result, which can be at most m + n in length.

And we are done.