Leetcode: Add Two Numbers

Add Two Numbers | LeetCode OJ

When we need to add two large numbers that cannot be cast in any of the builtin types we will need to use custom made data structures. We can use strings or linked list to store them. In this case we are given two numbers in the form of linked lists and we need to add them.

1. Use a dummy node as head of the result
2. Initialize the carry to 0
3. Now loop until atleast one of the list has nodes left or carry is set
4. At each step add values from both the list and the carry and calculate the new carry
5. Append new node at the end of the list and move the last node forward

Remarks:

1. Time complexity is same as the length of the larger list as we need to loop that many times
2. Similarly space complexity is the same as we need to add as many nodes as the length of larger list

Related Questions:

1. Handle negative integer inputs
2. Implement multiplication

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        res, carry = ListNode(0), 0
        n = res
        while l1 or l2 or carry:
            if l1:
                carry, l1 = carry + l1.val, l1.next
            if l2:
                carry, l2 = carry + l2.val, l2.next
            carry, val = divmod(carry, 10)
            n.next = ListNode(val)
            n = n.next
        return res.next