Double a Number Represented as a Linked List

Problem Description

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.

Key Insights

• The linked list represents a number where each node contains a single digit.
• Doubling the number may cause overflow into the next digit (e.g., 9 doubled becomes 18).
• We need to handle carries when doubling each digit.
• The final linked list may have more digits than the original linked list.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the linked list, as we need to traverse each node once. Space Complexity: O(1) - no additional space is used that scales with the input size.

Solution

To solve this problem, we will use:

• A single pass through the linked list to double each digit.
• A variable to keep track of the carry when a digit exceeds 9.
• A dummy node to facilitate the construction of the new linked list.

1. Initialize a dummy node to help build the new linked list.
2. Traverse the original linked list, doubling each node's value and adding the carry from the previous node.
3. If the result exceeds 9, set the current node's value to (doubled value % 10) and update the carry.
4. After processing all nodes, if there is still a carry, create a new node with the carry value.
5. Return the next node of the dummy as the head of the new linked list.

Code Solutions