Problem statement

A non-negative integer is stored in a linked list, one decimal digit per node, with the most significant digit at the head. The number has no leading zeros, except for the number 0 itself, which is a single node.

Double the number and return the head of a linked list representing the result in the same form.

Example 1

Input: head = [1,8,9]
Output: [3,7,8]
Explanation: 189 * 2 = 378.

Example 2

Input: head = [9,9,9]
Output: [1,9,9,8]
Explanation: 999 * 2 = 1998 — the result has one more digit than the input.

Example 3

Input: head = [0]
Output: [0]
Explanation: 0 * 2 = 0.

Constraints

• The number of nodes in the list is in the range [1, 10^4]
• 0 <= Node.val <= 9
• The number has no leading zeros, except the number 0 itself

Hints for Double a Number Represented as a Linked List

1. Hint 1

   Doubling a digit d gives at most 18, so each position sends a carry of at most 1 to the position on its left.

2. Hint 2

   The carry into a digit comes from its right neighbour: it is 1 exactly when that neighbour is 5 or more.

3. Hint 3

   So each new digit is (2 * d) mod 10, plus 1 if the next node's digit is at least 5 — one left-to-right pass, with an extra leading 1 when the head digit is at least 5.

How to solve Double a Number Represented as a Linked List

Carries normally flow right to left, against the list's links. But when doubling, the carry a digit receives is decided by its right neighbour alone (1 if that digit is >= 5), so every digit can be finalised walking left to right.

Approach

1. If the head digit is at least 5, the result gains a digit: put a new node 0 in front of the head.
2. For each node: set its digit to (2 * d) mod 10, and add 1 if the next node exists and its (original) digit is at least 5.
3. Return the (possibly new) head.

Why it works

The carry out of a position when doubling is floor(2d / 10) plus the carry into it, and 2d + 1 <= 19 keeps that at most 1; moreover 2d + carry >= 10 exactly when d >= 5, whatever the incoming carry. So the carry each digit receives is a function of its right neighbour only, which the forward pass reads before overwriting it.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Converting to a built-in integer overflows: the number has up to 10^4 digits.
• Read the next node's digit before it is overwritten — the pass changes each node only after its left neighbour has looked at it.
• The number 0 stays a single node 0.

Reference solution

Python

from typing import Optional

def doubleIt(head: Optional[ListNode]) -> Optional[ListNode]:
    if head.val > 4:
        head = ListNode(0, head)
    cur = head
    while cur:
        cur.val = cur.val * 2 % 10
        if cur.next and cur.next.val > 4:
            cur.val += 1
        cur = cur.next
    return head

Java

public static ListNode doubleIt(ListNode head) {
    if (head.val > 4) head = new ListNode(0, head);
    for (ListNode cur = head; cur != null; cur = cur.next) {
        cur.val = cur.val * 2 % 10;
        if (cur.next != null && cur.next.val > 4) cur.val += 1;
    }
    return head;
}

C++

ListNode* doubleIt(ListNode* head) {
    if (head->val > 4) head = new ListNode(0, head);
    for (ListNode* cur = head; cur; cur = cur->next) {
        cur->val = cur->val * 2 % 10;
        if (cur->next && cur->next->val > 4) cur->val += 1;
    }
    return head;
}

JavaScript

var doubleIt = function(head) {
    if (head.val > 4) head = new ListNode(0, head);
    for (var cur = head; cur !== null; cur = cur.next) {
        cur.val = cur.val * 2 % 10;
        if (cur.next !== null && cur.next.val > 4) cur.val += 1;
    }
    return head;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Product of the Last K Numbers Medium
• Add 1 to a Number Represented as Linked List Medium
• Insert Greatest Common Divisors in Linked List Medium
• Add Two Numbers II Medium
• Add Two Numbers Medium
• Count Special Subsequences Medium