LeetCode 2816 - Double a Number Represented as a Linked List

This problem asks us to double a number represented as a singly linked list. Each node of the list contains a single digit, and the digits are stored in the order from most significant to least significant. For example, the list [1,8,9] represents the number 189.

leetcodemediumlinked-listmathstack

LeetCode Problem 2816

Difficulty: 🟡 Medium
Topics: Linked List, Math, Stack

Solution

Problem Understanding

This problem asks us to double a number represented as a singly linked list. Each node of the list contains a single digit, and the digits are stored in the order from most significant to least significant. For example, the list [1,8,9] represents the number 189. The task is to compute 2 * number and return it as a linked list in the same format.

The input guarantees that the list is non-empty, represents a non-negative integer, and does not have leading zeros unless the number is 0. The number of nodes can be as large as 10,000, which rules out converting the list to an integer directly if the language cannot handle arbitrarily large numbers efficiently. The output should be a linked list that correctly represents the doubled number, including carrying over digits when necessary.

Important edge cases include numbers that cause a carry to a new most significant digit, for example doubling [9,9,9] produces [1,9,9,8], and the smallest input [0] which should return [0]. The problem also tests linked lists with maximum length to check efficiency.

Approaches

The brute force approach would convert the linked list to an integer, double it, and then convert the integer back into a linked list. This works correctly but is potentially inefficient for very large numbers because converting large integers could be costly in terms of time and memory.

A more optimal approach leverages linked list manipulation directly, avoiding the need to convert to and from integers. Since the digits are stored from most to least significant, doubling requires iterating from the least significant digit to the most significant. To achieve this, a stack can store nodes temporarily so that we can process them in reverse order, apply the doubling with carry propagation, and reconstruct the list correctly. This approach ensures O(n) time and O(n) space while working directly on the list structure.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Convert list to integer, double, and rebuild the list
Optimal (Stack) O(n) O(n) Use stack to process digits in reverse order, propagate carry

Algorithm Walkthrough

  1. Initialize an empty stack and traverse the linked list from head to tail, pushing each node onto the stack. This allows us to process digits from least significant to most significant.

  2. Initialize a carry variable to 0.

  3. While the stack is not empty:

  4. Pop the top node (representing the current least significant digit).

  5. Multiply its value by 2 and add the current carry.

  6. Update the node's value to (2*val + carry) % 10.

  7. Update carry to (2*val + carry) // 10.

  8. After processing all nodes, if there is a remaining carry (for example 1), create a new node with this value and link it as the new head.

  9. Return the head of the updated linked list.

Why it works: The algorithm ensures that we correctly double each digit from least to most significant, carrying over any overflow. Using a stack preserves the original node order for reconstruction while processing from the least significant digit. This guarantees the result is accurate for all inputs, including those requiring an additional most significant digit.

Python Solution

# 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]:
        if not head:
            return None
        
        stack = []
        current = head
        while current:
            stack.append(current)
            current = current.next
        
        carry = 0
        while stack:
            node = stack.pop()
            total = node.val * 2 + carry
            node.val = total % 10
            carry = total // 10
        
        if carry > 0:
            new_head = ListNode(carry)
            new_head.next = head
            head = new_head
        
        return head

The Python implementation first pushes all nodes to a stack to reverse traversal order. Then it doubles each digit, handling the carry. Finally, if there is a leftover carry, a new node is prepended to the list.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func doubleIt(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    stack := []*ListNode{}
    current := head
    for current != nil {
        stack = append(stack, current)
        current = current.Next
    }

    carry := 0
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        total := node.Val*2 + carry
        node.Val = total % 10
        carry = total / 10
    }

    if carry > 0 {
        newHead := &ListNode{Val: carry, Next: head}
        head = newHead
    }

    return head
}

The Go implementation mirrors the Python version. It uses a slice as a stack to process nodes in reverse order, updates the node values, and handles any carry by prepending a new node if needed.

Worked Examples

Example 1: head = [1,8,9]

Stack Carry Node Val Updated Node Val
[1,8,9] 0 9 8, carry 1
[1,8] 1 8 7, carry 1
[1] 1 1 3, carry 0

Resulting list: [3,7,8].

Example 2: head = [9,9,9]

Stack Carry Node Val Updated Node Val
[9,9,9] 0 9 8, carry 1
[9,9] 1 9 9, carry 1
[9] 1 9 9, carry 1

Prepend new node with carry: [1,9,9,8].

Complexity Analysis

Measure Complexity Explanation
Time O(n) We traverse the list twice: once to push nodes to stack, once to process doubling and carry.
Space O(n) Stack stores all nodes for reverse processing.

This is optimal for the problem because every node must be processed, and using a stack is necessary for handling carry propagation from least to most significant digit.

Test Cases

# Provided examples
assert Solution().doubleIt(ListNode(1, ListNode(8, ListNode(9)))).__dict__ == [3,7,8].__dict__  # 189*2=378
assert Solution().doubleIt(ListNode(9, ListNode(9, ListNode(9)))).__dict__ == [1,9,9,8].__dict__  # 999*2=1998

# Edge cases
assert Solution().doubleIt(ListNode(0)).__dict__ == [0].__dict__  # 0*2=0
assert Solution().doubleIt(ListNode(5)).__dict__ == [1,0].__dict__  # 5*2=10
assert Solution().doubleIt(ListNode(1, ListNode(0, ListNode(0, ListNode(0))))).__dict__ == [2,0,0,0].__dict__  # 1000*2=2000

# Large number
large_head = ListNode(9)
current = large_head
for _ in range(9999):
    current.Next = ListNode(9)
    current = current.Next
doubled = Solution().doubleIt(large_head)
assert doubled is not None  # just testing it handles max length
Test Why
[1,8,9] Normal multi-digit number
[9,9,9] Carry propagating to new head
[0] Minimal input
[5] Single-digit doubling creating carry
[1,0,0,0] Leading zeros after doubling handled
Large 10,000 digits Stress test maximum constraint

Edge Cases

One edge case is the smallest input [0]. A naive implementation might try to remove leading zeros or mishandle zero multiplication, but our solution correctly returns [0].

Another important edge case is when doubling produces an extra digit, such as [9,9,9]. This tests whether the algorithm correctly propagates carry and creates a new most significant node if necessary.

A third edge case is a long list at the maximum constraint. This ensures the algorithm handles large inputs without integer overflow or performance degradation, which our stack-based approach efficiently manages.