LeetCode Solutions Blog

Plus One Linked List

Number: 369

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a non-negative integer represented as a linked list of digits, where the most significant digit is at the head of the list, add one to the integer and return the modified list.

Key Insights

The digits are stored such that the most significant digit comes first, but addition is easier starting from the least significant digit.
Reversing the list allows simpler management of the carry during addition.
After processing the addition, reversing the list back restores the original order.
Consider special cases where all digits are 9, requiring a new head node to accommodate an additional digit.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the list
Space Complexity: O(1) extra space when using an iterative reversal method. (O(n) if recursion is used)

Solution

We solve the problem by first reversing the linked list, which converts it to a format where the least significant digit is processed first. We then iterate over the reversed list, adding one and managing any carry. If we encounter a carry at the end of the list, a new node is appended to handle the overflow. Finally, we reverse the list again to restore the original order. This method efficiently handles the addition with constant extra space during processing.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Helper function to reverse the linked list
def reverseList(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next  # store next node
        curr.next = prev  # reverse pointer
        prev = curr       # move prev forward
        curr = nxt        # move to next node
    return prev

def plusOne(head: ListNode) -> ListNode:
    # Reverse the linked list to start addition from the least significant digit
    head = reverseList(head)
    
    current = head
    carry = 1  # initialize carry as the plus one
    while current and carry:
        current.val += carry       # add carry to the current node
        carry = current.val // 10  # calculate new carry
        current.val %= 10          # update the node's value
        # If we're at the end and there's still a carry, create a new node.
        if not current.next and carry:
            current.next = ListNode(0)
        current = current.next
    
    # Reverse the list back to its original order before returning.
    return reverseList(head)