Double a Number Represented as a Linked List
MedPrompt
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:
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:
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
0itself.
Approaches
4 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a
BigIntegervariablenumberto zero. - Traverse the linked list from the
head. - In each step, update the
numberby the formula:number = number * 10 + node.val. - After the traversal, multiply the
numberby 2. - Convert the resulting
BigIntegerto its string representation. - Create a new dummy
headfor the result list. - Iterate through the characters of the string, create a new
ListNodefor each digit, and append it to the result list. - Return the
nextnode of the dummyhead.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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
BigIntegermultiplications.The constraints of the problem (up to 10^4 nodes) make standard integer types like
longoverflow, necessitating the use of aBigIntegerlibrary which might not be desirable or available.
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.
Algorithm
- Traverse the input linked list and push each node's value onto a stack.
- Initialize a
carryvariable to 0 and anewListHeadpointer tonull. - Loop until the stack is empty and the
carryis 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.
- Pop a value from the stack if it's not empty. Calculate
- Return
newListHead.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- First, implement a helper function
reverseListto reverse a linked list. - Call
reverseListon the inputheadto reverse the list. The original tail is now the head. - Traverse the reversed list, maintaining a
carryvariable 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
carryis greater than 0, append a new node with the carry's value to the end of the list (attail.next). - Reverse the list again using
reverseListto restore its original order. - Return the head of the doubly reversed list.
Walkthrough
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:
- Reverse the input linked list.
- 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.
- 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.
/** * 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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Check if the value of the
headnode is greater than 4. If it is, the doubled number will have an extra digit. To handle this, prepend a newListNode(0)to the list and updateheadto point to this new node. - Initialize a pointer
currentto thehead. - Iterate through the list as long as
currentis not null:- Calculate the base doubled value:
doubledValue = current.val * 2. - Look ahead to the next node. If
current.nextis not null andcurrent.next.valis 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.
- Calculate the base doubled value:
- Return the
headof the modified list.
Walkthrough
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.
/** * 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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
/** * 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 ; } }/** * 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 ; } };# 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 )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.