Watch 10 video solutions for Double a Number Represented as a Linked List, a medium level problem involving Linked List, Math, Stack. This walkthrough by codestorywithMIK has 5,551 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[1, 104]0 <= Node.val <= 90 itself.Problem Overview: You are given a linked list where each node stores a single digit of a non‑negative integer. The most significant digit appears first. The task is to double the number and return the resulting linked list while preserving the same digit-by-digit structure.
The main difficulty is handling carry when doubling digits. Since the list stores the most significant digit first, carries propagate toward the left side of the list, which makes a simple forward traversal tricky.
Approach 1: Stack-Based Simulation (O(n) time, O(n) space)
This approach treats the linked list like a number where digits must be processed from right to left. Traverse the list once and push each node onto a stack. Then pop nodes one by one and double the digit using basic math. Maintain a carry variable while computing newDigit = (digit * 2 + carry) % 10 and update carry = (digit * 2 + carry) / 10. Because the stack reverses processing order, carry propagation becomes straightforward. If a carry remains after processing all nodes, insert a new head node. This method is intuitive and mirrors how manual multiplication works, though it uses extra memory for the stack.
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
The optimized approach avoids extra space by managing carry during a forward traversal. Start with a dummy node before the head in case the most significant digit generates a carry. Traverse the list with a pointer while keeping track of the last node whose value is not 9. When doubling a digit produces a carry, increment that stored node and set all nodes between it and the current node to zero. This works because any digit 9 doubled becomes 18, forcing carry propagation. By remembering the last "safe" node (not equal to 9), you can adjust earlier digits without reversing the list. The algorithm completes in a single pass and only uses a few pointers.
Recommended for interviews: The two-pointer technique is usually the expected solution because it achieves O(n) time with O(1) extra space. The stack method demonstrates clear understanding of digit-by-digit arithmetic and carry handling, but interviewers typically prefer the in-place pointer solution for linked list problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Simulation | O(n) | O(n) | Simple implementation when reverse processing of digits is easier to reason about |
| Two-Pointer Technique | O(n) | O(1) | Preferred interview solution when minimizing extra memory is required |