Medium

Add Two Numbers II

LAB

Two non-empty linked lists store non-negative integers in forward digit order. Return the sum as a linked list encoded in forward digit order.

EXAMPLES

Example 1

Input
{
  "l1": [
    7,
    2,
    4,
    3
  ],
  "l2": [
    5,
    6,
    4
  ]
}

Output
[
  7,
  8,
  0,
  7
]

FUNCTION SHAPE

l1: intArrayl2: intArray→intArray

SOLUTION NOTE

This is a reminder: try to make connections with similar problems you've solved in the past. Reduction is a powerful problem solving technique, which involves massaging the current problem X in order to provide the correct inputs to a known problem solution Y, and then massaging the output of Y to solve X.

Reveal reference solution +

pythonREFERENCE

def reverse(self, curr):
    prev = None
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    return prev

def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    return self.reverse(self.addTwoNumbersI(self.reverse(l1), self.reverse(l2)))

# there are stored left to right...
# can reduce to Add Two Numbers I, by reversing both.
# and then reverse the answer

TimeO(max(n, m))

SpaceO(max(n, m))

Open on LeetCode ↗