445. Add Two Numbers II.md

445. Add Two Numbers II (Medium)

[tag] reverse linked list, two pointers

the linked list has the same order with the number.
1 2 0
+ 2 0
1 4 0

• method 1
  • need to figure out a way to reverse them and add them together.
  • it needs O(n) time at least. reverse them is also O(n).
  • O(n) space complexity.
• method 2
  • go through 7 2 4 3 and save it as a number
  • go through 5 6 4 and save the value.
  • add them and then store them use a new linked list. '''

Method 1

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        r1 = self.reverse(l1)
        r2 = self.reverse(l2)
        return self.add_linked_list(r1, r2)    
    # l1 l2 l3 l4
    # r1
    def reverse(self, l1):
        r1 = None
        temp = l1
        while(temp):
            original_next = temp.next
            temp.next = r1
            r1 = temp
            temp = original_next
        return r1
    
    def add_linked_list(self, r1, r2):
        temp_node = None
        temp1, temp2 = r1, r2
        carry = 0
        while(temp1 or temp2 or carry):
            if temp1:
                carry += temp1.val
                temp1 = temp1.next
            if temp2:
                carry += temp2.val
                temp2 = temp2.next                
            number = carry % 10
            carry //= 10
            new_node = ListNode(number)
            new_node.next = temp_node
            temp_node = new_node
        return temp_node   

Method 2

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        
        p1, p2 = l1, l2
        num1, num2 = 0, 0
        while p1:
            num1 = num1*10 + p1.val
            p1 = p1.next
        while p2:
            num2 = num2 * 10 + p2.val
            p2 = p2.next
        ans = num1 + num2
        print(ans)
        # dummy = ListNode()
        temp = None
        if ans == 0:
            return ListNode(0)
        while ans:
            new_node = ListNode(ans % 10)
            new_node.next = temp
            temp = new_node
            ans //= 10
        return temp