2816. Double a Number Represented as a Linked List

MediumStackLinked ListMath
Leetcode Link

Problem Description

You are provided with the head node of a non-empty singly linked list, which represents a non-negative integer written in reverse order — the first node represents the least significant digit, and there are no leading zeroes. The task is to return the head node of the modified linked list that represents the original number multiplied by two.

Intuition

The operation of doubling a number represented by a linked list is analogous to the process of multiplying an integer by two. However, since linked lists organize digits in reverse order and do not allow random access like arrays, we must handle the multiplication and carryover processes from the least significant digit (at the head of the reversed list) to the most significant digit in a linear fashion.

The solution to this problem involves these steps:

  1. Reverse the Linked List: We begin by reversing the original linked list. This rearrangement ensures the head of our new list represents the most significant digit of the number, thereby allowing us to perform multiplication from left to right as we normally would on paper.

  2. Multiply Each Digit: Going through each digit (node) from left to right, we multiply by two (as stated in the problem) and handle the carryover. For each node, we calculate the product of the node's value and two and add any carried-over value from multiplying the previous node.

  3. Handle Carries and Create Nodes: Since the result of multiplication for a single digit can be a two-digit number, we keep track of the carry (which can be 0 or 1 because the largest possible product of two digits is 18 when doubling 9 with a carry of 1). The single digit of the current product is stored as the value of the node, and the tens digit is carried over to the next multiplication.

  4. Adding the Last Carry: After all nodes have been processed, if there's a remaining carry (above 0), a new node will be created to hold that value.

  5. Reverse the Result: Reverse the resulting list back so that it's in the original format required by the problem, with the head node representing the least significant digit.

This approach efficiently carries out the doubling operation, despite the constraints of using a linked list data structure.

Learn more about Stack, Linked List and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which technique can we use to find the middle of a linked list?

Solution Approach

The solution follows the intuition described earlier. Here's a step-by-step walk-through correlating with the code provided:

  1. Reverse the input Linked List: The reverse function takes the head of a list as an argument and iteratively reverses the list. It uses a dummy head node to simplify the edge cases and proceeds by iterating over the list, re-linking the nodes in reverse order. At each step, the current node's next pointer is pointed to the node following the dummy, and then the dummy's next pointer is updated to the current node. This process is repeated until all nodes have been relinked in reverse order.

  2. Multiply the digits and handle carries: The doubleIt function then initializes mul = 2 for doubling and carry = 0 for initially no carryover. It iterates over the reversed linked list:

    • For each node, it calculates x = head.val * mul + carry, where head.val is the current digit.
    • The carry is updated to carry = x // 10, which represents the tens place of the result (can be either 0 or 1).
    • A new node is created with the digit x % 10 (the ones place of the result) and is linked to the result list.

  3. Add final carry if exists: After multiplying all digits, if there's any remaining carry, a new node with this carry value is appended to the result list.

  4. Reverse the result to the correct order: Finally, the function calls reverse on the result list to bring back the desired order, with the head node representing the least significant digit.

The algorithm makes use of simple list manipulation techniques, requires no additional data structure other than the linked list nodes themselves, and follows a straightforward simulation of the multiplication process on paper. The reversing pattern is essential for dealing with the list's inherent reversed digit order, and the linear iteration enables handling of carries in a direct, intuitive manner.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example Walkthrough

Let's use a small example to illustrate the solution approach. Assume we have a linked list representing the number 123 in reverse order, that is, the linked list is 3 -> 2 -> 1. We want to apply the solution approach to return a new list that represents the number 246 in reverse order, which should be 6 -> 4 -> 2.

Step 1: Reverse the Linked List We reverse the original list. Before: 3 -> 2 -> 1 After reversal: 1 -> 2 -> 3

Step 2: Multiply Each Digit and Handle Carries We now iterate through the reversed list, multiplying each digit by two and handling any carry.

  1. Starting from the head, multiply 1 * 2 = 2. No carry, so the new list is 2.
  2. Next, 2 * 2 = 4. No carry from the previous node, so we just add 4 to the new list: 2 -> 4.
  3. Finally, 3 * 2 = 6. Again, no carry, so we add 6 to the list: 2 -> 4 -> 6.

Since we have no carry left after the final multiplication, we can proceed to the next step.

Step 3: Add Final Carry if Exists There is no final carry in our case, so we can skip this step.

Step 4: Reverse the Result to the Correct Order Lastly, we reverse the linked list to return the digits to their original representation order while keeping the result doubled. Before: 2 -> 4 -> 6 After reversal: 6 -> 4 -> 2

The final linked list represents the number 246 in reverse order as required. This completes our example, demonstrating how the algorithm doubles a number represented as a linked list.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7class Solution:
8    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
9        # Helper function to reverse the linked list.
10        def reverse(node):
11            dummy = ListNode()
12            current = node
13            while current:
14                next_node = current.next
15                current.next = dummy.next
16                dummy.next = current
17                current = next_node
18            return dummy.next
19      
20        # Step 1: Reverse the input list to make it easier to double the digits from the least significant digit.
21        head = reverse(head)
22      
23        # Initialize a new dummy head for the result list.
24        dummy = current = ListNode()
25        multiplier = 2  # The factor by which we want to multiply each node's value.
26        carry = 0  # Initialize the carry for multiplication.
27      
28        # Step 2: Traverse the reversed list, doubling each digit and managing the carry.
29        while head:
30            product = head.val * multiplier + carry  # Multiply the current value and add the carry.
31            carry = product // 10  # Update carry for the next iteration.
32            current.next = ListNode(product % 10)  # Create a new node with the single digit.
33            current = current.next  # Move to the next position in the result list.
34            head = head.next  # Move to the next node in the input list.
35      
36        # Step 3: If there is a carry left after the loop, add it as a new node.
37        if carry:
38            current.next = ListNode(carry)
39      
40        # Step 4: Reverse the result list back to original order and return.
41        return reverse(dummy.next)
42
1class Solution {
2  
3    // Method to double the value of each node in a linked list
4    public ListNode doubleIt(ListNode head) {
5        // First, reverse the given linked list to start multiplication from the least significant digit
6        head = reverse(head);
7        // Create a dummy node to simplify result list construction
8        ListNode dummy = new ListNode();
9        ListNode current = dummy; // This will be used to add new nodes to the result list
10        int multiplier = 2; // The value by which we want to multiply each digit
11        int carry = 0; // To hold the carry value that results from multiplication
12      
13        // Traverse the reversed list to multiply each digit
14        while (head != null) {
15            int product = head.val * multiplier + carry; // Multiply the current node's value and add carry
16            carry = product / 10; // Compute carry for the next iteration
17            current.next = new ListNode(product % 10); // Store the single digit result in the new list
18            current = current.next; // Move current pointer forward
19            head = head.next; // Move to the next node in the input list
20        }
21      
22        // If carry remains after processing all digits, add a new node with the carry value
23        if (carry > 0) {
24            current.next = new ListNode(carry);
25        }
26      
27        // Finally, reverse the result list to restore original order and return
28        return reverse(dummy.next);
29    }
30
31    // Helper method to reverse a singly-linked list
32    private ListNode reverse(ListNode head) {
33        ListNode dummy = new ListNode(); // Dummy node to simplify list reversal
34        ListNode current = head; // Pointer to traverse the original list
35        // Iterate over the original list and reverse the links
36        while (current != null) {
37            ListNode next = current.next; // Remember the next node
38            current.next = dummy.next; // Make current node point to the beginning of the new reversed list
39            dummy.next = current; // Update the beginning of the reversed list to be the current node
40            current = next; // Move to the next node in the original list
41        }
42        // Return the reversed list, excluding the dummy node
43        return dummy.next;
44    }
45}
46
1// Definition for singly-linked list.
2struct ListNode {
3    int val;
4    ListNode *next;
5    ListNode(int x = 0, ListNode *pNext = nullptr) : val(x), next(pNext) {}
6};
7
8class Solution {
9public:
10    ListNode* doubleIt(ListNode* head) {
11        // Step 1: Reverse the input list to make it easier to handle carry operations.
12        head = reverse(head);
13      
14        // Create a dummy head to simplify the node insertion process.
15        ListNode* dummy = new ListNode();
16        ListNode* current = dummy;
17      
18        // Initialize multiplier to 2 for doubling the list values.
19        const int multiplier = 2;
20        int carry = 0; // To handle carry over during addition.
21
22        // Step 2: Traverse the reversed list, doubling each node's value.
23        while (head) {
24            int product = head->val * multiplier + carry;
25            carry = product / 10;
26            current->next = new ListNode(product % 10);
27            current = current->next;
28            head = head->next; // Move to the next node.
29        }
30
31        // Step 3: If there's a carry after the last multiplication, add a new node for it.
32        if (carry) {
33            current->next = new ListNode(carry);
34        }
35
36        // Step 4: Reverse the list again to restore the original order.
37        return reverse(dummy->next);
38    }
39
40    // Helper function to reverse a linked list.
41    ListNode* reverse(ListNode* head) {
42        // Create a dummy head to simplify the node insertion process.
43        ListNode* dummy = new ListNode();
44        ListNode* current = head;
45      
46        // Traverse the list and reverse the links.
47        while (current) {
48            ListNode* next = current->next; // Store next node.
49            // Insert the current node at the beginning of the reversed list.
50            current->next = dummy->next;
51            dummy->next = current;
52            // Move to the next node in the original list.
53            current = next;
54        }
55        // Return the head of the reversed list.
56        return dummy->next;
57    }
58};
59
1// Node definition for a singly-linked list.
2class ListNode {
3    val: number;
4    next: ListNode | null;
5
6    constructor(val?: number, next?: ListNode | null) {
7        this.val = val === undefined ? 0 : val;
8        this.next = next === undefined ? null : next;
9    }
10}
11
12/**
13 * Takes the head of a linked list, doubles the number it represents,
14 * and returns the head of the modified linked list.
15 * @param {ListNode | null} head - The head of the linked list.
16 * @returns {ListNode | null} - The head of the modified linked list.
17 */
18function doubleIt(head: ListNode | null): ListNode | null {
19    // Reverse the linked list to process its digits from the least significant digit.
20    head = reverse(head);
21    const dummyHead = new ListNode();
22    let currentNode = dummyHead;
23    const multiplier = 2; // The number to multiple each digit by.
24    let carry = 0; // Initialize carry to 0 for addition.
25
26    // Iterate through the linked list, doubling each digit and handling the carry.
27    while (head) {
28        const product = head.val * multiplier + carry;
29        carry = Math.floor(product / 10);
30        currentNode.next = new ListNode(product % 10);
31        currentNode = currentNode.next;
32        head = head.next;
33    }
34
35    // If there is a carry left after the last digit, add a new node for it.
36    if (carry) {
37        currentNode.next = new ListNode(carry);
38    }
39
40    // Reverse the result to restore the original order and return.
41    return reverse(dummyHead.next);
42}
43
44/**
45 * Reverses a singly-linked list and returns the new head.
46 * @param {ListNode | null} head - The head of the linked list to be reversed.
47 * @returns {ListNode | null} - The head of the reversed linked list.
48 */
49function reverse(head: ListNode | null): ListNode | null {
50    const dummyHead = new ListNode();
51    let currentNode = head;
52
53    // Iterate through the list and reverse the pointers.
54    while (currentNode) {
55        const nextNode = currentNode.next;
56        currentNode.next = dummyHead.next;
57        dummyHead.next = currentNode;
58        currentNode = nextNode;
59    }
60
61    // Return the new head of the reversed list.
62    return dummyHead.next;
63}
64
Not Sure What to Study? Take the 2-min Quiz：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Time and Space Complexity

The given function doubleIt modifies a linked list by doubling each element within it. The algorithm can be analyzed for time and space complexity as follows:

Time Complexity

The time complexity of the code is O(n) where n is the number of nodes in the linked list. This complexity arises from several operations that each take linear time:

  1. The reverse function traverses all the nodes of the linked list once to reverse it. This operation is O(n).

  2. The next section of the code involving multiplication and building the new result linked list also takes linear time since it processes each node exactly once. Each operation inside the while loop takes constant time, and the loop runs for n iterations: O(n).

  3. The reverse function is called again to reverse the modified list back to the original order. This is another O(n) operation.

Since these operations are sequential, the overall time complexity is the sum of individual complexities: O(n) + O(n) + O(n) which simplifies to O(n).

Space Complexity

For space complexity, we exclude the space taken by the input and output from consideration, as is standard in complexity analysis.

  1. The reverse function uses a constant amount of extra space (a few pointers) that does not depend on the size of the list, so it is O(1).

  2. In the main part of the function, apart from the input and the result, we use a constant amount of variables (dummy, cur, mul, carry, next, x). Hence, the space complexity remains O(1).

The reference answer confirms the analysis of both time complexity O(n) and the space complexity O(1) for the given code.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫