# Double a Number Represented as a Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/double-a-number-represented-as-a-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/double-a-number-represented-as-a-linked-list
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Linked List, Stack
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia)
---
## Problem
You are given the `head` of a **non-empty** linked list representing a non-negative integer without leading zeroes.

Return _the_ `head` _of the linked list after **doubling** it_.

**Example 1:**

![](https://assets.glich.co/dsa/double-a-number-represented-as-a-linked-list/image0.png) 

**Input:** head = [1,8,9]
**Output:** [3,7,8]
**Explanation:** The figure above corresponds to the given linked list which represents the number 189. Hence, the returned linked list represents the number 189 * 2 = 378.

**Example 2:**

![](https://assets.glich.co/dsa/double-a-number-represented-as-a-linked-list/image1.png) 

**Input:** head = [9,9,9]
**Output:** [1,9,9,8]
**Explanation:** The figure above corresponds to the given linked list which represents the number 999. Hence, the returned linked list reprersents the number 999 * 2 = 1998. 

**Constraints:**

* The number of nodes in the list is in the range `[1, 104]`
* `0 <= Node.val <= 9`
* The input is generated such that the list represents a number that does not have leading zeros, except the number `0` itself.

# Approaches
## Convert to BigInteger, Double, and Convert Back
This approach converts the linked list representation of the number into a `BigInteger`, doubles it, and then converts the result back into a new linked list. It's conceptually simple but very inefficient for large numbers due to the overhead of `BigInteger` operations, making it impractical for the given constraints.
**Time:** O(N^2), where N is the number of nodes. Building the `BigInteger` involves multiplications that take time proportional to the number of digits, leading to a quadratic time complexity. · **Space:** O(N), where N is the number of nodes. This space is used to store the `BigInteger` representation, its string form, and the new linked list.
**Pros:** The logic is very simple and easy to understand.; It leverages powerful, built-in libraries for handling large numbers.
**Cons:** Highly inefficient with a time complexity of O(N^2) due to repeated `BigInteger` multiplications.; The constraints of the problem (up to 10^4 nodes) make standard integer types like `long` overflow, necessitating the use of a `BigInteger` library which might not be desirable or available.
### Explanation
The most straightforward way to approach this problem is to treat it as a standard arithmetic problem. We first convert the linked list, which represents the number digit by digit, into an actual integer data type. Since the number of digits can be up to 10,000, we must use a data type that supports arbitrary-precision arithmetic, such as Java's `BigInteger`.

Once the number is in `BigInteger` form, we can simply multiply it by two. The final step is to convert this doubled number back into a linked list. We can do this by first converting the `BigInteger` to a string, and then creating a new linked list where each node corresponds to a digit in the string.

```java
import java.math.BigInteger;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode doubleIt(ListNode head) {
        if (head == null) {
            return null;
        }

        // 1. Convert list to BigInteger
        BigInteger number = BigInteger.ZERO;
        ListNode current = head;
        while (current != null) {
            number = number.multiply(BigInteger.TEN).add(BigInteger.valueOf(current.val));
            current = current.next;
        }

        // 2. Double the number
        number = number.multiply(BigInteger.valueOf(2));

        // 3. Convert back to linked list
        String s = number.toString();
        ListNode newHead = new ListNode(0);
        ListNode tail = newHead;
        for (char c : s.toCharArray()) {
            tail.next = new ListNode(c - '0');
            tail = tail.next;
        }

        return newHead.next;
    }
}
```
### Algorithm
- Initialize a `BigInteger` variable `number` to zero.
- Traverse the linked list from the `head`.
- In each step, update the `number` by the formula: `number = number * 10 + node.val`.
- After the traversal, multiply the `number` by 2.
- Convert the resulting `BigInteger` to its string representation.
- Create a new dummy `head` for the result list.
- Iterate through the characters of the string, create a new `ListNode` for each digit, and append it to the result list.
- Return the `next` node of the dummy `head`.

## Stack-Based Right-to-Left Calculation
To correctly handle carries, multiplication should be performed from the least significant digit (right) to the most significant (left). Since a singly linked list is traversed left-to-right, we can use a stack to reverse the order of processing. This approach is much more efficient than the `BigInteger` method but requires extra space.
**Time:** O(N), where N is the number of nodes. We perform one pass to push values onto the stack and another pass to pop them and build the new list. · **Space:** O(N), where N is the number of nodes. The stack stores N values, and the new result list also takes O(N) space.
**Pros:** Efficient O(N) time complexity.; Correctly handles the arithmetic without using large number libraries.
**Cons:** Requires O(N) extra space for the stack, which can be significant for a large list.
### Explanation
This method simulates the way we do multiplication by hand. We start from the rightmost digit, double it, and carry over any excess to the next digit on the left. To achieve this right-to-left processing on a singly linked list, we can use a stack.

First, we iterate through the linked list from head to tail, pushing each node's value onto a stack. Now, the top of the stack holds the least significant digit.

Next, we process the digits by popping from the stack. We maintain a `carry` variable. In each step, we pop a digit, double it, add the carry, and calculate the new digit (`sum % 10`) and the new carry (`sum / 10`). We create a new node for the new digit and prepend it to our result list. This process of prepending naturally builds the new list in the correct left-to-right order.

We continue until the stack is empty and there's no final carry left. This method correctly computes the result in linear time.

```java
import java.util.Stack;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode doubleIt(ListNode head) {
        Stack<Integer> values = new Stack<>();
        ListNode current = head;
        while (current != null) {
            values.push(current.val);
            current = current.next;
        }

        ListNode listTail = null;
        int carry = 0;
        
        while (!values.isEmpty() || carry != 0) {
            int sum = carry;
            if (!values.isEmpty()) {
                sum += values.pop() * 2;
            }
            
            // Prepend the new node to the result list
            ListNode newNode = new ListNode(sum % 10);
            newNode.next = listTail;
            listTail = newNode;
            
            carry = sum / 10;
        }
        
        return listTail;
    }
}
```
### Algorithm
- Traverse the input linked list and push each node's value onto a stack.
- Initialize a `carry` variable to 0 and a `newListHead` pointer to `null`.
- Loop until the stack is empty and the `carry` is 0:
  - Pop a value from the stack if it's not empty. Calculate `sum = (popped_value * 2) + carry`.
  - If the stack is empty, `sum = carry`.
  - Create a new node with the value `sum % 10`.
  - Prepend this new node to the result list: `newNode.next = newListHead; newListHead = newNode;`.
  - Update the carry: `carry = sum / 10`.
- Return `newListHead`.

## In-Place Modification with Reversal
This approach achieves an optimal O(1) space complexity by performing the doubling in-place. It first reverses the list to allow for a simple right-to-left calculation (which becomes a left-to-right traversal on the reversed list). After the calculation, the list is reversed back to its original order.
**Time:** O(N), where N is the number of nodes. The list is traversed three times in total (two reversals, one calculation pass), resulting in a linear time complexity. · **Space:** O(1). The list reversal and doubling are performed in-place, using only a few extra pointers.
**Pros:** Optimal O(1) space complexity as the operation is done in-place.; Efficient O(N) time complexity.
**Cons:** The list is modified twice (two reversals), which adds some overhead and complexity.; This approach is not suitable if the original list structure must be preserved for other concurrent operations.
### Explanation
To avoid the O(N) space complexity of the stack-based approach, we can modify the list in-place. The main obstacle to an in-place, left-to-right traversal is handling the carry, which propagates from right to left. By reversing the linked list, we can traverse it from the least significant digit to the most significant digit easily.

The process involves three main steps:
1.  Reverse the input linked list.
2.  Traverse the reversed list, performing the doubling operation. For each node, we update its value and calculate the carry for the next node. This is done in-place. If a final carry remains after traversing all nodes, we append a new node for it.
3.  Reverse the list again to restore the correct order of digits.

This method cleverly uses list reversal to enable a simple, in-place calculation, resulting in optimal space usage.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode doubleIt(ListNode head) {
        // 1. Reverse the list
        ListNode reversedHead = reverseList(head);
        
        // 2. Double the values with carry
        int carry = 0;
        ListNode current = reversedHead;
        ListNode tail = null;
        
        while (current != null) {
            int doubledVal = current.val * 2 + carry;
            current.val = doubledVal % 10;
            carry = doubledVal / 10;
            tail = current; // Keep track of the last node
            current = current.next;
        }
        
        // 3. Handle final carry
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        
        // 4. Reverse back
        return reverseList(reversedHead);
    }
    
    private ListNode reverseList(ListNode node) {
        ListNode prev = null;
        ListNode curr = node;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}
```
### Algorithm
- First, implement a helper function `reverseList` to reverse a linked list.
- Call `reverseList` on the input `head` to reverse the list. The original tail is now the head.
- Traverse the reversed list, maintaining a `carry` variable initialized to 0.
- For each node, calculate `doubledVal = node.val * 2 + carry`.
- Update the node's value in-place: `node.val = doubledVal % 10`.
- Update the carry for the next iteration: `carry = doubledVal / 10`.
- Keep a pointer to the last visited node (`tail`).
- After the loop, if `carry` is greater than 0, append a new node with the carry's value to the end of the list (at `tail.next`).
- Reverse the list again using `reverseList` to restore its original order.
- Return the head of the doubly reversed list.

## Optimal Single Pass Approach with Lookahead
This is the most efficient approach, achieving the result in a single pass over the linked list with constant extra space. It cleverly uses a lookahead to the next node to determine if a carry will be generated, allowing it to update the current node's value correctly in one go without needing to reverse the list or use a stack.
**Time:** O(N), where N is the number of nodes. The list is traversed only once. · **Space:** O(1). The modification is done in-place. At most, one extra node is created if the number of digits increases.
**Pros:** Most efficient with O(N) time complexity in a single pass.; Optimal O(1) space complexity.; Elegant solution that avoids complex list manipulations like reversal.
**Cons:** The lookahead logic might be slightly less intuitive to grasp initially compared to methods that explicitly process from right to left.
### Explanation
This optimal solution avoids both list reversals and extra space by performing the calculation in a single left-to-right pass. The key insight is that when we are at a node `current`, its final value is determined by `current.val * 2` plus a potential carry from the node to its right, `current.next`.

A carry of 1 is generated from `current.next` if and only if `current.next.val * 2 >= 10`, which simplifies to `current.next.val > 4`. So, for each node, we can calculate its doubled value and add 1 if its successor's value is 5 or greater. The node's new value is then the result modulo 10.

A special case is the head of the list. If `head.val > 4`, the total number of digits will increase. We can handle this gracefully by prepending a sentinel node `new ListNode(0)` to the list before starting the process. This sentinel node will automatically become `1` if a carry is propagated from the original head, and we can simply return it as the new head.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode doubleIt(ListNode head) {
        // If the head's value > 4, the doubled list will have a new head node.
        // Prepending a sentinel node simplifies this case.
        if (head.val > 4) {
            head = new ListNode(0, head);
        }
        
        ListNode current = head;
        while (current != null) {
            int doubledValue = current.val * 2;
            
            // If the next node exists and its value is > 4, a carry will be generated.
            if (current.next != null && current.next.val > 4) {
                doubledValue += 1;
            }
            
            current.val = doubledValue % 10;
            current = current.next;
        }
        
        return head;
    }
}
```
### Algorithm
- Check if the value of the `head` node is greater than 4. If it is, the doubled number will have an extra digit. To handle this, prepend a new `ListNode(0)` to the list and update `head` to point to this new node.
- Initialize a pointer `current` to the `head`.
- Iterate through the list as long as `current` is not null:
  - Calculate the base doubled value: `doubledValue = current.val * 2`.
  - Look ahead to the next node. If `current.next` is not null and `current.next.val` is greater than 4, it means a carry will be generated. Add this carry: `doubledValue += 1`.
  - Update the current node's value with the units digit of the result: `current.val = doubledValue % 10`.
  - Move to the next node: `current = current.next`.
- Return the `head` of the modified list.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode doubleIt ( ListNode head ) { head = reverse ( head ); ListNode dummy = new ListNode (); ListNode cur = dummy ; int mul = 2 , carry = 0 ; while ( head != null ) { int x = head . val * mul + carry ; carry = x / 10 ; cur . next = new ListNode ( x % 10 ); cur = cur . next ; head = head . next ; } if ( carry > 0 ) { cur . next = new ListNode ( carry ); } return reverse ( dummy . next ); } private ListNode reverse ( ListNode head ) { ListNode dummy = new ListNode (); ListNode cur = head ; while ( cur != null ) { ListNode next = cur . next ; cur . next = dummy . next ; dummy . next = cur ; cur = next ; } return dummy . next ; } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * doubleIt ( ListNode * head ) { head = reverse ( head ); ListNode * dummy = new ListNode (); ListNode * cur = dummy ; int mul = 2 , carry = 0 ; while ( head ) { int x = head -> val * mul + carry ; carry = x / 10 ; cur -> next = new ListNode ( x % 10 ); cur = cur -> next ; head = head -> next ; } if ( carry ) { cur -> next = new ListNode ( carry ); } return reverse ( dummy -> next ); } ListNode * reverse ( ListNode * head ) { ListNode * dummy = new ListNode (); ListNode * cur = head ; while ( cur ) { ListNode * next = cur -> next ; cur -> next = dummy -> next ; dummy -> next = cur ; cur = next ; } return dummy -> next ; } };
```

### Python

```python
# 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 ]: def reverse ( head ): dummy = ListNode () cur = head while cur : next = cur . next cur . next = dummy . next dummy . next = cur cur = next return dummy . next head = reverse ( head ) dummy = cur = ListNode () mul , carry = 2 , 0 while head : x = head . val * mul + carry carry = x // 10 cur . next = ListNode ( x % 10 ) cur = cur . next head = head . next if carry : cur . next = ListNode ( carry ) return reverse ( dummy . next )
```