Jobs

Interviews

Discussions

Double a Number Represented as a Linked List

Medium

Asked by:

More companies

67 views

Topics:

Linked Lists

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, 10⁴]
0 <= Node.val <= 9
The input is generated such that the list represents a number that does not have leading zeros, except the number 0 itself.

Try coding it in LeetCode

Double a Number Represented as a Linked List

Medium

Asked by:

67 views

Topics:

Linked Lists

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, 10⁴]
0 <= Node.val <= 9
The input is generated such that the list represents a number that does not have leading zeros, except the number 0 itself.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty or contain only a single node?
Can the digits in the linked list nodes be any integer, or are they limited to single digits (0-9)?
Is the linked list representing the number in forward order (most significant digit first) or reverse order (least significant digit first)?
Should the returned linked list be a new linked list, or can I modify the existing one in place?
Are there any memory constraints that I should be aware of when creating a new linked list?

Brute Force Solution

Approach

We're given a number represented as a linked list, and we want to double that number. The brute force method is like converting the number to its usual decimal form, doubling it, and then converting it back to a linked list.

Here's how the algorithm would work step-by-step:

First, walk through the entire linked list to reconstruct the full number it represents.
Then, simply multiply that number by two. This is the doubling part.
Finally, take the doubled number and build a new linked list where each digit of the number becomes a separate element in the list.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def double_linked_list_brute_force(head):
    # Convert the linked list to a number.
    current_node = head
    number_as_string = ""
    while current_node:
        number_as_string += str(current_node.value)
        current_node = current_node.next_node
    
    if not number_as_string:
        return None

    number = int(number_as_string)
    doubled_number = number * 2

    # Convert the doubled number back to a linked list.
    doubled_number_string = str(doubled_number)
    new_head = ListNode(int(doubled_number_string[0]))
    current_node = new_head

    # Build the new linked list
    for digit_index in range(1, len(doubled_number_string)):
        digit = int(doubled_number_string[digit_index])
        new_node = ListNode(digit)
        current_node.next_node = new_node
        current_node = new_node

    return new_head

Big(O) Analysis

Time Complexity

O(n) – Let n be the number of digits in the linked list. The first step involves traversing the linked list once to reconstruct the number, which takes O(n) time. Doubling the number itself is a constant-time operation, O(1). Converting the doubled number back into a linked list requires iterating through the digits of the doubled number, which in the worst case, has n+1 digits, hence this step also takes O(n) time. Thus, the overall time complexity is O(n) + O(1) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm first constructs a decimal number from the linked list, which doesn't contribute to auxiliary space significantly. However, after doubling this number, it creates a new linked list to represent the doubled value. The new linked list will have at most N+1 nodes, where N is the number of nodes in the original linked list because doubling can at most increase the number of digits by one. Therefore, the auxiliary space required is proportional to the number of nodes in the linked list and is O(N).

Optimal Solution

Approach

We want to double a number that's stored as a linked list, one digit per node. The key idea is to simulate the multiplication process we learned in elementary school, working from right to left, handling carries along the way. This approach efficiently updates the list in place, representing the doubled number.

Here's how the algorithm would work step-by-step:

Start from the end of the linked list, which represents the least significant digit of the number.
Double the digit at that position.
If doubling the digit results in a value greater than 9, we need to carry over the tens digit to the next position to the left.
Update the current digit to be the ones digit of the doubled value (the remainder after dividing by 10).
Move to the previous digit (the next node to the left) and repeat the process, remembering to add the carry if there was one.
Continue moving left, doubling each digit and handling carries until you reach the beginning of the list.
If, after doubling the most significant digit, you still have a carry, add a new node at the beginning of the list to represent this carry.
The linked list now represents the doubled number, read from left to right.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def double_linked_list(head):
    current_node = head
    number_list = []
    while current_node:
        number_list.append(current_node)
        current_node = current_node.next

    carry = 0
    for i in range(len(number_list) - 1, -1, -1):
        current_digit = number_list[i].val
        doubled_digit = 2 * current_digit + carry

        # Handle the carry-over if the doubled digit is greater than 9.
        number_list[i].val = doubled_digit % 10
        carry = doubled_digit // 10

        # If carry remains after doubling the most significant digit,
    if carry:
        new_head = ListNode(carry)
        new_head.next = head
        head = new_head

    return head

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once from the last node to the first node. In each iteration, it performs a constant number of operations: doubling the digit, checking for carry, and updating the node's value. The number of iterations is directly proportional to the number of nodes (n) in the linked list. Thus, the time complexity is linearly proportional to the size of the linked list.

Space Complexity

O(1) – The algorithm modifies the linked list in place. While it uses a 'carry' variable to store a single digit, this is independent of the size of the input linked list (N, where N is the number of nodes in the list). No auxiliary data structures that scale with the input size are used; the space required for the carry remains constant regardless of how many digits are in the number. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty linked list as input	Return a new linked list with a single node containing 0.
Linked list representing a single-digit number	Multiply the single digit by 2, handle carry if any, and create the new linked list accordingly.
Linked list representing a number with leading zeros	The algorithm should correctly process the linked list without being affected by leading zeros, preserving their place value during multiplication.
Large number represented by the linked list that could lead to integer overflow during multiplication	The digit-by-digit multiplication and carry-over method prevents integer overflow, as it processes digits individually.
Linked list representing a number with many digits (scalability)	The solution's iterative approach scales linearly with the number of digits, making it efficient for large numbers.
Carry-over occurring in the most significant digit	Append a new node with the carry value to the beginning of the result linked list if the final carry is non-zero.
Linked list representing the number 0	Return a new linked list with a single node containing 0.
Negative numbers represented in linked list format.	The problem context assumes a positive number, therefore a negative input is invalid, and should be addressed by returning an error or defining that negative numbers should be converted to positive.

Empty linked list as input

How to Handle:

Return a new linked list with a single node containing 0.

Linked list representing a single-digit number

How to Handle:

Multiply the single digit by 2, handle carry if any, and create the new linked list accordingly.

Linked list representing a number with leading zeros

How to Handle:

The algorithm should correctly process the linked list without being affected by leading zeros, preserving their place value during multiplication.

Large number represented by the linked list that could lead to integer overflow during multiplication

How to Handle:

The digit-by-digit multiplication and carry-over method prevents integer overflow, as it processes digits individually.

Linked list representing a number with many digits (scalability)

How to Handle:

The solution's iterative approach scales linearly with the number of digits, making it efficient for large numbers.

Carry-over occurring in the most significant digit

How to Handle:

Append a new node with the carry value to the beginning of the result linked list if the final carry is non-zero.

Linked list representing the number 0

How to Handle:

Return a new linked list with a single node containing 0.

Negative numbers represented in linked list format.

How to Handle:

The problem context assumes a positive number, therefore a negative input is invalid, and should be addressed by returning an error or defining that negative numbers should be converted to positive.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty or contain only a single node?
Can the digits in the linked list nodes be any integer, or are they limited to single digits (0-9)?
Is the linked list representing the number in forward order (most significant digit first) or reverse order (least significant digit first)?
Should the returned linked list be a new linked list, or can I modify the existing one in place?
Are there any memory constraints that I should be aware of when creating a new linked list?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, walk through the entire linked list to reconstruct the full number it represents.
Then, simply multiply that number by two. This is the doubling part.
Finally, take the doubled number and build a new linked list where each digit of the number becomes a separate element in the list.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def double_linked_list_brute_force(head):
    # Convert the linked list to a number.
    current_node = head
    number_as_string = ""
    while current_node:
        number_as_string += str(current_node.value)
        current_node = current_node.next_node
    
    if not number_as_string:
        return None

    number = int(number_as_string)
    doubled_number = number * 2

    # Convert the doubled number back to a linked list.
    doubled_number_string = str(doubled_number)
    new_head = ListNode(int(doubled_number_string[0]))
    current_node = new_head

    # Build the new linked list
    for digit_index in range(1, len(doubled_number_string)):
        digit = int(doubled_number_string[digit_index])
        new_node = ListNode(digit)
        current_node.next_node = new_node
        current_node = new_node

    return new_head

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start from the end of the linked list, which represents the least significant digit of the number.
Double the digit at that position.
If doubling the digit results in a value greater than 9, we need to carry over the tens digit to the next position to the left.
Update the current digit to be the ones digit of the doubled value (the remainder after dividing by 10).
Move to the previous digit (the next node to the left) and repeat the process, remembering to add the carry if there was one.
Continue moving left, doubling each digit and handling carries until you reach the beginning of the list.
If, after doubling the most significant digit, you still have a carry, add a new node at the beginning of the list to represent this carry.
The linked list now represents the doubled number, read from left to right.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def double_linked_list(head):
    current_node = head
    number_list = []
    while current_node:
        number_list.append(current_node)
        current_node = current_node.next

    carry = 0
    for i in range(len(number_list) - 1, -1, -1):
        current_digit = number_list[i].val
        doubled_digit = 2 * current_digit + carry

        # Handle the carry-over if the doubled digit is greater than 9.
        number_list[i].val = doubled_digit % 10
        carry = doubled_digit // 10

        # If carry remains after doubling the most significant digit,
    if carry:
        new_head = ListNode(carry)
        new_head.next = head
        head = new_head

    return head

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty linked list as input	Return a new linked list with a single node containing 0.
Linked list representing a single-digit number	Multiply the single digit by 2, handle carry if any, and create the new linked list accordingly.
Linked list representing a number with leading zeros	The algorithm should correctly process the linked list without being affected by leading zeros, preserving their place value during multiplication.
Large number represented by the linked list that could lead to integer overflow during multiplication	The digit-by-digit multiplication and carry-over method prevents integer overflow, as it processes digits individually.
Linked list representing a number with many digits (scalability)	The solution's iterative approach scales linearly with the number of digits, making it efficient for large numbers.
Carry-over occurring in the most significant digit	Append a new node with the carry value to the beginning of the result linked list if the final carry is non-zero.
Linked list representing the number 0	Return a new linked list with a single node containing 0.
Negative numbers represented in linked list format.	The problem context assumes a positive number, therefore a negative input is invalid, and should be addressed by returning an error or defining that negative numbers should be converted to positive.

Empty linked list as input

How to Handle:

Return a new linked list with a single node containing 0.

Linked list representing a single-digit number

How to Handle:

Multiply the single digit by 2, handle carry if any, and create the new linked list accordingly.

Linked list representing a number with leading zeros

How to Handle:

The algorithm should correctly process the linked list without being affected by leading zeros, preserving their place value during multiplication.

Large number represented by the linked list that could lead to integer overflow during multiplication

How to Handle:

The digit-by-digit multiplication and carry-over method prevents integer overflow, as it processes digits individually.

Linked list representing a number with many digits (scalability)

How to Handle:

The solution's iterative approach scales linearly with the number of digits, making it efficient for large numbers.

Carry-over occurring in the most significant digit

How to Handle:

Append a new node with the carry value to the beginning of the result linked list if the final carry is non-zero.

Linked list representing the number 0

How to Handle:

Return a new linked list with a single node containing 0.

Negative numbers represented in linked list format.

How to Handle:

The problem context assumes a positive number, therefore a negative input is invalid, and should be addressed by returning an error or defining that negative numbers should be converted to positive.