Python O(n) with Two Stacks, Beat 91.23%


  • 0
    Z
    def addTwoNumbers(self, l1, l2):
        # push to two stacks s1,s2
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1=l1.next
        while l2:
            s2.append(l2.val)
            l2=l2.next
        # define summation and list node
        sm, ls = 0, ListNode(0)
        while s1 or s2:
            if s1: sm += s1.pop()
            if s2: sm += s2.pop()
            ls.val = sm % 10   # get remainder
            head = ListNode(sm/10)
            head.next = ls
            ls = head
            sm /= 10  # obtain 0 or 1 to be added
        return (ls.next if ls.val==0 else ls)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.