LC2816. Double a Number Represented as a Linked List

Approach 1: Multiple List Reversals

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        revHead = self.reverse(head)
 
        prev, curr = None, revHead
        carry = 0
        while curr:
            total = carry + curr.val * 2
            curr.val = total % 10
            carry = total // 10
            prev = curr
            curr = curr.next
        
        if carry:
            prev.next = ListNode(carry)
 
        return self.reverse(revHead)
    
    def reverse(self, node):
        prev = None
        while node:
            tmp = node.next
            node.next = prev
            prev = node
            node = tmp
        
        return prev

Complexity

Time: $O(n)$
Space: $O(1)$

Approach 1: Recursion + Carry

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        carry = self._doubleIt(head)
 
        if carry == 0:
            return head
        
        tmp = ListNode(carry, head)
        return tmp
 
    def _doubleIt(self, node):
        carry = 0
        if node.next:
            carry = self._doubleIt(node.next)
        
        total = node.val * 2 + carry
        node.val = total % 10
 
        return total // 10

Complexity

Time: $O(n)$
Space: $O(n)$

Approach 2: Recursion + Number Doubling (Suboptimal)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        remaining = self._doubleIt(head, 0)
 
        # If doubled number is same digits, return
        # head immediately
        if remaining == 0:
            return head
 
        # Otherwise construct new nodes for remaining
        # digits and return a new head
        tmp = head
        if remaining > 0:
            prev = tmp
            tmp = ListNode()
            tmp.val = remaining % 10
            tmp.next = prev
            remaining //= 10
        
        return tmp
 
    def _doubleIt(self, head, num):
        if not head:
            return num * 2
        
        doubled = self._doubleIt(head.next, num * 10 + head.val)
        head.val = doubled % 10
 
        return doubled // 10

Complexity

Time: $O(n)$
Space: $O(n)$

Notes

This won’t scale for languages that don’t support arbitrarily large integers. The doubling would overflow.

Other Languages