My struggle with Problem & Follow Up in Python


  • 0

    I call my solution "struggle" because I haven't figure out some tricky idea for the follow-up part except an naive one :)

    First part is solving this by reverse the two list first:

    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            def reverse(l):
                ans = dummy = ListNode(-1)
                dummy.next = None
                while l:
                    next = l.next
                    l.next = dummy.next
                    dummy.next = l
                    l = next
                return ans.next
                
            l1, l2 = reverse(l1), reverse(l2)
            ans = dummy = ListNode(-1)
            carry = 0
            while l1 or l2:
                carry ,val = (l2.val + carry) / 10 if not l1 else( (l1.val + carry) / 10 if not l2 else (l1.val + l2.val + carry) / 10), (l2.val + carry) % 10 if not l1 else ( (l1.val + carry) % 10 if not l2 else (l1.val + l2.val + carry) % 10 )
                l1, l2 = l1 if not l1 else l1.next, l2 if not l2 else l2.next
                dummy.next = ListNode(val)
                dummy = dummy.next
            val = None if not carry else ListNode(carry)
            dummy.next = val
            return reverse(ans.next)
    

    Then for the follow-up, I first figure out the "depth" of the current node, by depth I mean the distance for it to reach to the end of the list, for the convience of the recursion.

    class Solution(object):
        def addTwoNumbers(self, l1, l2):
            tl1, tl2, d1, d2 = l1, l2, 0, 0
            while tl1:
                d1 += 1
                tl1 = tl1.next
            while tl2:
                d2 += 1
                tl2 = tl2.next
                
            def add(la, da, lb, db):
                ans = (0, 0)
                if not la or not lb:
                    return (0, None)
                if da == db:
                    next = add(la.next, da - 1, lb.next, db - 1)
                    carry, ansval = (la.val + lb.val + next[0]) / 10, (la.val + lb.val + next[0]) % 10
                elif da > db:
                    next = add(la.next, da - 1, lb, db)
                    carry, ansval = (la.val + next[0]) / 10, (la.val + next[0]) % 10
                else:
                    next = add(la, da, lb.next, db - 1)
                    carry, ansval = (lb.val + next[0]) / 10, (lb.val + next[0]) % 10
                node = ListNode(ansval)
                node.next = next[1]
                return (carry, node)
            ans = add(l1, d1, l2, d2)
            answer = ListNode(ans[0])
            answer.next = ans[1]
            return answer if ans[0] else answer.next
    

Log in to reply
 

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