Jobs

Interviews

Discussions

Plus One Linked List

Medium

Google

6 views

Topics:

Linked Lists

You are given a singly linked list where each node represents a digit of a non-negative integer. The digits are stored in such a way that the most significant digit is at the head of the list. Your task is to increment the number represented by the linked list by one and return the head of the updated linked list.

For example:

Input: 1 -> 2 -> 3
Output: 1 -> 2 -> 4
Input: 4 -> 3 -> 2 -> 1
Output: 4 -> 3 -> 2 -> 2
Input: 9 -> 9 -> 9
Output: 1 -> 0 -> 0 -> 0
Input: 1 -> 9 -> 9
Output: 2 -> 0 -> 0

Explain your approach, analyze its time and space complexity, and provide code that efficiently solves this problem. Consider edge cases such as when the input list represents a number consisting entirely of 9s. How would you handle a very large number (e.g., a linked list with 1000 nodes) without running into integer overflow issues?

Plus One Linked List

Medium

Google

6 views

Topics:

Linked Lists

For example:

Input: 1 -> 2 -> 3
Output: 1 -> 2 -> 4
Input: 4 -> 3 -> 2 -> 1
Output: 4 -> 3 -> 2 -> 2
Input: 9 -> 9 -> 9
Output: 1 -> 0 -> 0 -> 0
Input: 1 -> 9 -> 9
Output: 2 -> 0 -> 0

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 null?
Can the linked list represent a number with leading zeros (e.g., 0 -> 1 -> 2)?
Does the linked list represent a non-negative number?
If the linked list represents a number consisting of all 9s (e.g., 9 -> 9 -> 9), should I create a new node at the head?
What is the maximum number of nodes expected in the linked list?

Brute Force Solution

Approach

We need to add one to a number represented as a linked list. The most straightforward way is to convert the linked list into a regular number, add one to it, and then convert the new number back into a linked list.

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

First, go through the linked list and build the complete number it represents. Think of it like reading the digits from left to right to form one big number.
Once you have the entire number, simply add one to it.
Now, take the new number and build a new linked list to represent it. Start with the least significant digit and work your way to the most significant digit, creating nodes for each digit as you go.

Code Implementation

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

def plus_one_linked_list(head):
    # Convert linked list to integer
    number_from_list = 0
    while head:
        number_from_list = number_from_list * 10 + head.val
        head = head.next

    # Add one to the integer
    number_from_list += 1

    # Handle the case where the number is zero
    if number_from_list == 0:
        return ListNode(0)

    # Convert integer back to linked list
    dummy_head = ListNode(0)
    current_node = dummy_head

    # We construct the linked list in reverse order
    number_as_string = str(number_from_list)
    for digit in number_as_string:
        current_node.next = ListNode(int(digit))
        current_node = current_node.next

    # The dummy node is removed, but we must do so after the list has been created.
    return dummy_head.next

Big(O) Analysis

Time Complexity

O(n) – The first step involves traversing the linked list of n nodes to construct an integer. This takes O(n) time. Next, adding one to the integer is O(1). Finally, converting the incremented integer back to a linked list requires creating n nodes in the worst case (e.g., when all digits are 9 and we need to add a new leading 1), which takes O(n) time. Therefore, the overall time complexity is dominated by the two O(n) operations, making it O(n).

Space Complexity

O(N) – The space complexity is O(N) because the algorithm converts the linked list to a number which doesn't require extra space (only a constant number of variables). However, converting the resulting number back to a linked list requires creating a new linked list. The new linked list will have at most N+1 nodes, where N is the number of nodes in the original linked list because adding one to the number represented by the original list can at most increase the length of the number by one digit. Therefore, the space complexity is proportional to the number of nodes in the resulting linked list, which is O(N).

Optimal Solution

Approach

We need to add one to a number represented as a linked list. The efficient way is to traverse the list from the end, adding one and handling any carry-over to the next digit until either the carry-over is resolved or we reach the start of the list.

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

Start at the last digit of the linked list.
Add one to that last digit.
If the result is greater than nine, set the digit to zero and carry-over one to the next digit to the left.
Move to the next digit to the left and repeat the addition, including any carry-over from the previous digit.
Continue until you reach the start of the linked list or there's no carry-over.
If, after processing all digits, there's still a carry-over (meaning the original number was all nines, like 999), create a new node at the beginning of the list with the value of one.

Code Implementation

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

def plus_one_linked_list(head):
    sentinel_head = ListNode(0)
    sentinel_head.next = head
    not_nine = sentinel_head

    current_node = head
    while current_node:
        if current_node.val != 9:
            not_nine = current_node
        current_node = current_node.next

    # Increment the rightmost non-nine digit
    not_nine.val += 1

    # Set all the following nines to zero
    current_node = not_nine.next
    while current_node:
        current_node.val = 0
        current_node = current_node.next

    # If the sentinel node is not zero, it means we had all nines
    if sentinel_head.val != 0:
        return sentinel_head
    else:
        return sentinel_head.next

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list at most once. In the best case (e.g., the last digit isn't 9), it only modifies the last node, which would be O(1). However, in the worst case (e.g., the entire list consists of 9s), it iterates through all n nodes of the linked list to propagate the carry. If a new node is needed at the beginning, that's still a constant time operation. Therefore, the time complexity is driven by the single traversal of the list, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm primarily manipulates the existing linked list nodes in place. It uses a few variables to keep track of the carry-over and potentially a pointer during reversal, but the number of these variables remains constant regardless of the number of nodes (N) in the linked list. The only possible extra space is for a single new node at the beginning of the list in the case where the original number was all nines, but even this is a constant amount of space. Thus, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty linked list (head is null)	Return a new linked list with a single node containing the value 1, as adding one to zero is one.
Linked list representing a number with all 9s (e.g., 9 -> 9 -> 9)	Handle the carry propagation correctly by adding a new node with value 1 at the beginning if the carry remains after processing all digits.
Single-digit linked list representing the number 9	Change the node's value to 0 and prepend a new node with value 1 to the list.
Integer overflow during carry propagation (language specific, but important to consider if using a less common language)	The linked list representation inherently avoids integer overflow issues since each node stores only a single digit.
Negative numbers in the linked list (invalid input according to the problem)	Throw an IllegalArgumentException or return null, indicating that negative numbers are not supported.
Maximum-sized linked list allowed by memory constraints	Ensure the algorithm uses constant extra space (O(1)) and avoids unnecessary memory allocations to prevent memory errors for extremely large lists.
Linked list with leading zeros (e.g., 0 -> 0 -> 1 -> 2 -> 3)	The problem deals with adding one to the number the list represents; leading zeros are handled as if they were not there by ignoring them.
Very long linked list where iterative solution may cause stack overflow in some language (though linked lists aren't typically that long)	An iterative approach should be preferred over a recursive approach to avoid potential stack overflow issues with exceptionally long linked lists.

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 null?
Can the linked list represent a number with leading zeros (e.g., 0 -> 1 -> 2)?
Does the linked list represent a non-negative number?
If the linked list represents a number consisting of all 9s (e.g., 9 -> 9 -> 9), should I create a new node at the head?
What is the maximum number of nodes expected in the linked list?

Brute Force Solution

Approach

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

First, go through the linked list and build the complete number it represents. Think of it like reading the digits from left to right to form one big number.
Once you have the entire number, simply add one to it.
Now, take the new number and build a new linked list to represent it. Start with the least significant digit and work your way to the most significant digit, creating nodes for each digit as you go.

Code Implementation

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

def plus_one_linked_list(head):
    # Convert linked list to integer
    number_from_list = 0
    while head:
        number_from_list = number_from_list * 10 + head.val
        head = head.next

    # Add one to the integer
    number_from_list += 1

    # Handle the case where the number is zero
    if number_from_list == 0:
        return ListNode(0)

    # Convert integer back to linked list
    dummy_head = ListNode(0)
    current_node = dummy_head

    # We construct the linked list in reverse order
    number_as_string = str(number_from_list)
    for digit in number_as_string:
        current_node.next = ListNode(int(digit))
        current_node = current_node.next

    # The dummy node is removed, but we must do so after the list has been created.
    return dummy_head.next

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the last digit of the linked list.
Add one to that last digit.
If the result is greater than nine, set the digit to zero and carry-over one to the next digit to the left.
Move to the next digit to the left and repeat the addition, including any carry-over from the previous digit.
Continue until you reach the start of the linked list or there's no carry-over.
If, after processing all digits, there's still a carry-over (meaning the original number was all nines, like 999), create a new node at the beginning of the list with the value of one.

Code Implementation

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

def plus_one_linked_list(head):
    sentinel_head = ListNode(0)
    sentinel_head.next = head
    not_nine = sentinel_head

    current_node = head
    while current_node:
        if current_node.val != 9:
            not_nine = current_node
        current_node = current_node.next

    # Increment the rightmost non-nine digit
    not_nine.val += 1

    # Set all the following nines to zero
    current_node = not_nine.next
    while current_node:
        current_node.val = 0
        current_node = current_node.next

    # If the sentinel node is not zero, it means we had all nines
    if sentinel_head.val != 0:
        return sentinel_head
    else:
        return sentinel_head.next

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty linked list (head is null)	Return a new linked list with a single node containing the value 1, as adding one to zero is one.
Linked list representing a number with all 9s (e.g., 9 -> 9 -> 9)	Handle the carry propagation correctly by adding a new node with value 1 at the beginning if the carry remains after processing all digits.
Single-digit linked list representing the number 9	Change the node's value to 0 and prepend a new node with value 1 to the list.
Integer overflow during carry propagation (language specific, but important to consider if using a less common language)	The linked list representation inherently avoids integer overflow issues since each node stores only a single digit.
Negative numbers in the linked list (invalid input according to the problem)	Throw an IllegalArgumentException or return null, indicating that negative numbers are not supported.
Maximum-sized linked list allowed by memory constraints	Ensure the algorithm uses constant extra space (O(1)) and avoids unnecessary memory allocations to prevent memory errors for extremely large lists.
Linked list with leading zeros (e.g., 0 -> 0 -> 1 -> 2 -> 3)	The problem deals with adding one to the number the list represents; leading zeros are handled as if they were not there by ignoring them.
Very long linked list where iterative solution may cause stack overflow in some language (though linked lists aren't typically that long)	An iterative approach should be preferred over a recursive approach to avoid potential stack overflow issues with exceptionally long linked lists.