LeetCode Solutions Blog

Double a Number Represented as a Linked List

Number: 2871

Difficulty: Medium

Paid? No

Problem Description

You are given the head of a non-empty linked list representing a non-negative integer without leading zeroes. Each node contains a single digit, where the most significant digit is at the head of the list. Your task is to double the number represented by the linked list and return the head of the resulting linked list.

Key Insights

Reversing the list simplifies processing the least significant digit first, making it easier to handle carry propagation.
Multiplying each digit by 2 and managing the carry is similar to the addition operation.
After processing, reverse the list again to restore the original order.
Watch out for an extra carry at the end which may create an additional node (e.g., doubling 999 results in 1998).

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list. Space Complexity: O(1) (ignoring the space required for the output linked list).

Solution

The solution follows these steps using linked list reversal:

Reverse the linked list so that you can start doubling from the least significant digit.
Traverse the reversed list, doubling each digit and adding any carry from the previous operation.
If a carry remains at the end of the traversal, append a new node to the list.
Reverse the list again to restore the original order. This approach leverages list reversal and in-place updates to efficiently double the number represented by the linked list.

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 reverse_list(head: ListNode) -> ListNode:
    prev = None
    current = head
    while current:
        next_node = current.next  # Save next node
        current.next = prev       # Reverse pointer to previous node
        prev = current            # Move prev to current node
        current = next_node       # Move to the next node
    return prev

def doubleLinkedList(head: ListNode) -> ListNode:
    # Step 1: Reverse the linked list.
    head = reverse_list(head)
    
    current = head
    carry = 0
    
    # Step 2: Process each node: double the value and handle carry.
    while current:
        doubled_value = current.val * 2 + carry  # Multiply digit by 2 and add carry
        current.val = doubled_value % 10         # Update current node with new value
        carry = doubled_value // 10              # Obtain new carry
        current = current.next

    # Step 3: If there is a remaining carry, append a new node.
    if carry:
        current = head
        while current.next:
            current = current.next
        current.next = ListNode(carry)

    # Step 4: Reverse the linked list back to the original order.
    head = reverse_list(head)
    return head