445. Add Two Numbers II (Python)

Related Topic

Linked-List. Stack.

Description

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

Follow Up:

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Sample I/O

Example 1

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

Methodology

This is an extention question of 02. Add Two Numbers The difference is now The most significant digit comes first

The brutal force solution will iterate both Linked List and take out dights store in array and reverse the array, 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,store in array, reverse array, combine number, insert back to Linked List will cause lots of operations and the performance is aweful. The code may also be complicated to read.

My solution will use stack. First, iterate L1 and L2 and store their digits into in l1, l2 stacks. Then, Pop the top from both stacks and do calculation to get value and asign the value to new created node. Create a head node init it as None. We point head’s next pointer to the new created node and update the new node become head node. Finally we return head node.

Code

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack_l1 = []
        stack_l2 = []
        while l1:
            stack_l1.append(l1)
            l1 = l1.next
        while l2:
            stack_l2.append(l2)
            l2 = l2.next
        carry = 0
        head = None
        while stack_l1 or stack_l2:
            v1 = stack_l1.pop().val if stack_l1 else 0
            v2 = stack_l2.pop().val if stack_l2 else 0
            v = v1 + v2
            carry, v = divmod(v+carry, 10)
            temp = head
            head = ListNode(v)
            head.next = temp
        if carry:
            temp = head
            head = ListNode(carry)
            head.next = temp
        return head

BigO

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