Leetcode 445. Add Two Numbers II

📅2023-07-18🧐56

https://leetcode.com/problems/add-two-numbers-ii/description/

Intuitively, we could add the pointer of previous node the input linked lists in space. Since we need to reverse both of them, let's create a function to do this.

def addPrevPointer(head):
  prev, curr, _head = None, head, head

  while curr:
      curr.prev = prev
      prev = curr
      curr = curr.next

  return _head, prev

head1, tail1 = addPrevPointer(l1)
head2, tail2 = addPrevPointer(l2)

Then, we could start the calculation from the tail of those linked lists. At first, I just think about the logic:

  1. both of linked lists have next node
  2. one of them has node left
  3. still a borrowed number there
# 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 addPrevPointer(head):
            prev, curr, _head = None, head, head

            while curr:
                curr.prev = prev
                prev = curr
                curr = curr.next

            return _head, prev

        head1, tail1 = addPrevPointer(l1)
        head2, tail2 = addPrevPointer(l2)
            

        new_tail = ListNode()
        curr = new_tail
        curr1, curr2 = tail1, tail2
        borrow = 0

        while curr1 and curr2:
            val = curr1.val + curr2.val + borrow
            curr.prev = ListNode(val % 10)
            borrow = val // 10
            curr.prev.next = curr
            curr = curr.prev
            curr1 = curr1.prev
            curr2 = curr2.prev

        while curr1:
            val = curr1.val + borrow
            curr.prev = ListNode(val % 10)
            borrow = val // 10
            curr.prev.next = curr
            curr = curr.prev
            curr1 = curr1.prev

        while curr2:
            val = curr2.val + borrow
            curr.prev = ListNode(val % 10)
            borrow = val // 10
            curr.prev.next = curr
            curr = curr.prev
            curr2 = curr2.prev

        if borrow:
            curr.prev = ListNode(borrow)
            curr.prev.next = curr
            curr = curr.prev

        new_tail.prev.next = None

        return curr

Actually there are some duplicated code, we could optimize this solution to make it looks concise:

# 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 addPrevPointer(head):
            prev, curr, _head = None, head, head

            while curr:
                curr.prev = prev
                prev = curr
                curr = curr.next

            return _head, prev

        head1, tail1 = addPrevPointer(l1)
        head2, tail2 = addPrevPointer(l2)
            

        new_tail = ListNode()
        curr = new_tail
        curr1, curr2 = tail1, tail2
        borrow = 0

        while curr1 or curr2:
            val = borrow
            if curr1:
                val += curr1.val
            if curr2:
                val += curr2.val

            curr.prev = ListNode(val % 10)
            borrow = val // 10

            curr.prev.next = curr
            curr = curr.prev
            if curr1:
                curr1 = curr1.prev
            if curr2:
                curr2 = curr2.prev

        if borrow:
            curr.prev = ListNode(borrow)
            curr.prev.next = curr
            curr = curr.prev

        new_tail.prev.next = None

        return curr

Also, a last-in-first-out data structure: stack also can be used in this problem.