2. Add Two Numbers

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/add-two-numbers/
• topics: Linked List

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Fast recursive solution that reuses nodes of l1 and l2

# 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]:
        if not l1 or not l2:
            return l1 if l1 else l2
 
        def addList2ToList1(l1, l2, residual):
            if l1 is None and l2 is None:
                return ListNode(residual) if residual else None
 
            if l1 is None:
                l1 = l2
                l2 = None
 
            s = l1.val + residual + (l2.val if l2 else 0)
            l1.val = s % 10 
            l1.next = addList2ToList1(l1.next, (l2.next if l2 else None), s // 10)
            return l1
        
        return addList2ToList1(l1, l2, 0)