Python AC recursive solution with reversing lists


  • 0
    W

    It might be a little cheating, but really easy and intuitive.

    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            if not (l1 and l2): return l1 or l2
            # reverse lists:
            r1,r2 = self._rev(l1),self._rev(l2)
            # regular addition
            r = self._add(r1,r2)
            # return reversed regular addition
            return self._rev(r)
            
        def _rev(self,head,prev=None):
            if not head: return prev
            t = head.next
            head.next = prev
            return self._rev(t, prev = head)
        
        def _add(self, l1, l2):
            if not (l1 and l2): return l1 or l2
            tot = l1.val+l2.val
            val,carry = tot if tot<10 else tot-10,0 if tot<10 else 1
            new = ListNode(val)
            new.next = self._add(l1.next, l2.next) if not carry else \
                       self._add(ListNode(1), self._add(l1.next,l2.next))
            return new
    # runtime 122 ms
    # 79.55%
    

Log in to reply
 

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