Problem Description

You are given the head of a non-empty linked list where the nodes together represent a non-negative integer without leading zeroes. Each node contains a single digit (0-9), and the digits are arranged from most significant to least significant when reading from head to tail.

Your task is to double the integer value represented by the linked list and return the head of a new linked list representing the doubled value.

For example:

• If the linked list represents 189 (nodes: 1 → 8 → 9), doubling it gives 378 (nodes: 3 → 7 → 8)
• If the linked list represents 999 (nodes: 9 → 9 → 9), doubling it gives 1998 (nodes: 1 → 9 → 9 → 8)

The solution works by:

1. Reversing the linked list - This makes it easier to handle carry propagation since we can process from least significant digit to most significant digit
2. Performing multiplication with carry handling - Each digit is multiplied by 2, and any carry from the previous operation is added. The result's last digit becomes the new node value, and any overflow becomes the carry for the next iteration
3. Handling final carry - If there's a remaining carry after processing all digits, a new node is added
4. Reversing back - The result is reversed again to restore the proper order (most significant digit first)

The key insight is that reversing the list allows us to handle the multiplication naturally from right to left (least significant to most significant), just like how we would multiply on paper.

Intuition

When we need to double a number represented as a linked list, we face a fundamental challenge: multiplication naturally proceeds from right to left (least significant digit to most significant), but linked lists are traversed from left to right.

Think about how you would double 189 on paper:

  189
×   2
-----
  378

You start from the rightmost digit: 9 × 2 = 18, write down 8 and carry 1. Then 8 × 2 + 1 = 17, write down 7 and carry 1. Finally 1 × 2 + 1 = 3, write down 3.

The problem is that in a singly linked list, we can't easily traverse backwards. We could use recursion to reach the end and process on the way back, but that would use O(n) stack space.

The key insight is to reverse the linked list first. This transforms our problem:

• Original list: 1 → 8 → 9 (representing 189)
• After reversal: 9 → 8 → 1 (digits in reverse order)

Now we can traverse the reversed list normally while performing multiplication with carry propagation, exactly like the paper method. Each node we visit corresponds to the next digit we would process when multiplying by hand.

After multiplication:

• We get: 8 → 7 → 3 (representing 378 in reverse)
• Reverse again: 3 → 7 → 8 (the correct answer)

This approach elegantly sidesteps the traversal limitation by aligning the list's natural left-to-right traversal with the multiplication's right-to-left processing requirement. The two reversals (O(n) each) are a small price to pay for this simplification.

Learn more about Stack, Linked List and Math patterns.

Solution Approach

The solution implements the reverse linked list and simulation approach through three main steps:

Step 1: Reverse the Linked List

The reverse helper function reverses a linked list using the standard iterative approach:

def reverse(head):
    dummy = ListNode()
    cur = head
    while cur:
        next = cur.next         # Save next node
        cur.next = dummy.next   # Point current to previous reversed part
        dummy.next = cur        # Update dummy to point to current
        cur = next              # Move to next node
    return dummy.next

This uses a dummy node to simplify the reversal process. Each node is detached from the original list and inserted at the beginning of the new reversed list.

Step 2: Simulate Multiplication with Carry

After reversing the input list, we traverse it while maintaining:

• mul = 2: The multiplication factor
• carry = 0: Tracks overflow from previous digit multiplication
• dummy and cur: Build the result list

dummy = cur = ListNode()
mul, carry = 2, 0
while head:
    x = head.val * mul + carry  # Multiply digit and add carry
    carry = x // 10              # Calculate new carry (0 or 1)
    cur.next = ListNode(x % 10) # Create node with last digit
    cur = cur.next               # Move result pointer
    head = head.next             # Move input pointer

For each digit, we:

1. Calculate x = digit × 2 + carry
2. Extract the new carry using integer division: carry = x // 10
3. Create a new node with the ones digit: x % 10

Step 3: Handle Final Carry and Reverse Back

After processing all digits, if there's still a carry (meaning the number of digits increased), we add one more node:

if carry:
    cur.next = ListNode(carry)

Finally, we reverse the result list to restore the proper digit order:

return reverse(dummy.next)

Time and Space Complexity:

• Time: O(n) where n is the number of nodes - we traverse the list three times (reverse, multiply, reverse)
• Space: O(n) for creating the new result list

The elegance of this solution lies in transforming the problem through reversals, allowing us to handle carry propagation naturally while traversing the list in its standard direction.

Example Walkthrough

Let's walk through doubling the number 189 represented as a linked list: 1 → 8 → 9

Step 1: Reverse the Original List

Starting with 1 → 8 → 9, we reverse it to get 9 → 8 → 1

This allows us to process digits from least significant (9) to most significant (1).

Step 2: Multiply Each Digit with Carry Handling

Now we traverse the reversed list and multiply by 2:

• Process node 9:

  • Calculate: 9 × 2 + 0 (carry) = 18
  • New carry: 18 // 10 = 1
  • Create node with value: 18 % 10 = 8
  • Result so far: 8

• Process node 8:

  • Calculate: 8 × 2 + 1 (carry) = 17
  • New carry: 17 // 10 = 1
  • Create node with value: 17 % 10 = 7
  • Result so far: 8 → 7

• Process node 1:

  • Calculate: 1 × 2 + 1 (carry) = 3
  • New carry: 3 // 10 = 0
  • Create node with value: 3 % 10 = 3
  • Result so far: 8 → 7 → 3

Step 3: Check Final Carry

The carry is 0, so no additional node is needed.

Step 4: Reverse the Result

We have 8 → 7 → 3 (which represents 378 in reverse). Reversing it gives us 3 → 7 → 8, which correctly represents 378.

Final Answer: 3 → 7 → 8

This matches our expected result since 189 × 2 = 378.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the linked list. The algorithm performs three main operations:

1. First reverse() call traverses the entire list once: O(n)
2. The main while loop processes each node exactly once to perform multiplication: O(n)
3. Second reverse() call traverses the result list once: O(n)

Total time complexity: O(n) + O(n) + O(n) = O(n)

The space complexity is O(1) if we exclude the space required for the output linked list. The algorithm uses only a constant amount of extra space:

• A few pointer variables (dummy, cur, next, head) in the reverse function
• Variables mul, carry, and x for the multiplication logic
• Temporary ListNode objects for dummy nodes

All these variables use constant space regardless of the input size. The new linked list created for the result is not counted as it's part of the required output.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Final Carry

The Pitfall: One of the most common mistakes is forgetting to add the final carry after processing all digits. This happens when doubling a number causes it to gain an extra digit.

Example of the Bug:

# INCORRECT - Missing final carry handling
while reversed_head:
    product = reversed_head.val * multiplier + carry
    carry = product // 10
    current.next = ListNode(product % 10)
    current = current.next
    reversed_head = reversed_head.next
# Forgot to check if carry > 0 here!
return reverse_list(dummy.next)

When input is 999 (9→9→9), this would incorrectly return 998 instead of 1998, losing the leading 1.

The Fix: Always check for remaining carry after the main loop:

if carry:
    current.next = ListNode(carry)

2. Modifying the Original List Instead of Creating a New One

The Pitfall: Attempting to modify the original list in-place during reversal or multiplication operations, which can corrupt the input data or lead to infinite loops.

Example of the Bug:

# INCORRECT - Modifying original nodes
def doubleIt(self, head):
    head = reverse_list(head)
    current = head
    carry = 0
    while current:
        product = current.val * 2 + carry
        carry = product // 10
        current.val = product % 10  # Modifying original node!
        current = current.next

The Fix: Always create new nodes for the result:

current.next = ListNode(product % 10)  # Create new node

3. Incorrect Reversal Implementation

The Pitfall: Using an incorrect reversal algorithm that loses nodes or creates cycles. A common mistake is not properly tracking the next node before modifying pointers.

Example of the Bug:

# INCORRECT - Loses reference to rest of list
def reverse_list(head):
    prev = None
    while head:
        head.next = prev  # Lost reference to original head.next!
        prev = head
        head = head.next  # This is now None or prev

The Fix: Save the next node before modifying pointers:

def reverse_list(head):
    dummy = ListNode()
    current = head
    while current:
        next_node = current.next  # Save next first!
        current.next = dummy.next
        dummy.next = current
        current = next_node  # Use saved reference

4. Not Handling Edge Cases with Single Digit Overflow

The Pitfall: Assuming carry will always be at most 1, when in fact it can only be 0 or 1 for doubling operations (since max is 9 × 2 + 1 = 19).

Example of Potential Confusion:

# Overly complex - carry for doubling is always 0 or 1
if carry > 9:  # This will never happen
    # Unnecessary complex logic

The Fix: Keep it simple - carry for doubling will only be 0 or 1:

carry = product // 10  # Will be 0 or 1
current.next = ListNode(product % 10)