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.
This approach utilizes binary search to efficiently find the target element in a sorted array. Since the array is sorted, binary search can be applied, reducing the time complexity significantly compared to a linear search.
The core idea is to repeatedly divide the search interval in half. If the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half until the target is found or the interval is empty.
This C code implements a binary search. It initializes two pointers, left and right, and iteratively adjusts them based on comparisons with the middle element of the active subarray. When the target is found, it immediately returns the index. If not found, it returns -1.
Time Complexity: O(log n), where n is the number of elements in the array.
Space Complexity: O(1), as no extra space is utilized.
The two-pointer approach helps to solve the problem with pointers or two index variables. This technique is beneficial when you need to minimize the number of iterations or traverse the array with controlled steps. Often used in problems involving arrays, especially when the sum or difference needs to be calculated between distinct elements.
This C code solves the problem using two pointers: one pointing to the start of the array, and the other pointing to the end. If the sum of the values at these two pointers matches the target, a flag is set. Otherwise, the pointers are adjusted to optimize towards the condition.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as no extra space is consumed.
First, we reverse the linked list, then simulate the multiplication operation, and finally reverse the linked list back.
Time complexity is O(n), where n is the length of the linked list. Ignoring the space taken by the answer linked list, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time Complexity: O(log n), where n is the number of elements in the array. |
| Two-Pointer Technique | Time Complexity: O(n), where n is the number of elements in the array. |
| Reverse Linked List + Simulation | — |
| 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 |
Double a Number Represented as a Linked List | 4 Approaches | Story|Leetcode 2816 | codestorywithMIK • codestorywithMIK • 5,551 views views
Watch 9 more video solutions →Practice Double a Number Represented as a Linked List with our built-in code editor and test cases.
Practice on FleetCode