2. Add Two Numbers (Python)

Related Topic

Linked-List.

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 contain a single digit. Add the two numbers and return it as a linked list.

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

Sample I/O

Example 1

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Methodology

The brutal force solution will iterate both Linked List and take out dights, make them become a number then plus the two numbers to get the result number. Create a new LinkedList and insert the dights from result number, then return this LinkedList. However, take out digits from Linked List, combine number, insert back to Linked List will cause lots of operations. The code may be complicated to read.

My solution will iterate L1 and L2 to calculate current digit and carry at same time for their common length and insert the current digit to result Linked List. Do not forget update the head of the result Linked List! If there is one Linked List is longer than another, we concatenate the rest of the longer one to the result Linked List and keep calculating the carry and the current node value. At last, after done the iteration of result Linked List, if carry is not 0 then we just add another node with value equal = carry to the result Linked List.

Code

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        result = head = ListNode("inf")
        carry = 0
        while l1 and l2:
            carry, cur = divmod(l1.val + l2.val + carry, 10)
            node = ListNode(cur)
            head.next = node
            head, l1, l2 = head.next, l1.next, l2.next
        head.next = l1 if l1 else l2
        while carry and head.next:
            carry, cur = divmod(head.next.val + carry, 10)
            head.next.val = cur
            head = head.next
        if carry:
            head.next = ListNode(carry)
        return result.next

BigO

Iterate the linked list once, so total time complexity is O(n)