Double a Number Represented as a Linked List

medium linked list math

Problem

A non-negative integer is stored as a linked list with the most significant digit at the head (one digit per node, no leading zeros except the number 0 itself). Multiply that number by two and return the result as a linked list in the same most-significant-first order.

Inputhead = 1→8→9

Output3→7→8

The list represents 189, and 189 × 2 = 378, so the answer is 3→7→8.

head (digits comma-separated, MSB first)

def double_it(head):
    if head.val >= 5:
        head = ListNode(0, head)
    node = head
    while node:
        node.val = (node.val * 2) % 10
        if node.next and node.next.val >= 5:
            node.val += 1
        node = node.next
    return head

function doubleIt(head) {
  if (head.val >= 5) {
    head = { val: 0, next: head };
  }
  let node = head;
  while (node) {
    node.val = (node.val * 2) % 10;
    if (node.next && node.next.val >= 5) {
      node.val += 1;
    }
    node = node.next;
  }
  return head;
}

class Solution {
    public ListNode doubleIt(ListNode head) {
        if (head.val >= 5) {
            head = new ListNode(0, head);
        }
        ListNode node = head;
        while (node != null) {
            node.val = (node.val * 2) % 10;
            if (node.next != null && node.next.val >= 5) {
                node.val += 1;
            }
            node = node.next;
        }
        return head;
    }
}

ListNode* doubleIt(ListNode* head) {
    if (head->val >= 5) {
        head = new ListNode(0, head);
    }
    ListNode* node = head;
    while (node != nullptr) {
        node->val = (node->val * 2) % 10;
        if (node->next != nullptr && node->next->val >= 5) {
            node->val += 1;
        }
        node = node->next;
    }
    return head;
}

Explanation

Doubling a multi-digit number by hand means doubling each digit and carrying anything past nine into the digit to its left. Here the digits are stored most significant first, so the carry from one node always flows into the node before it (toward the head).

The neat observation is that doubling a single digit gives a value from 0 to 18, so the carry it produces is always either 0 or 1 — and that carry is 1 exactly when the digit is 5 or larger. That means we never have to look backward: while standing on a node, we can peek at its next node to decide whether a carry will arrive from the right.

First we handle the head. If the leading digit is 5 or more, doubling the whole number gains an extra digit, so we prepend a new node holding 0 in front of the head to make room for that carry.

Then we walk the list once. At each node we set node.val = (node.val * 2) % 10 (its own doubled digit, keeping only the ones place), and if the next node's original digit was 5 or more we add 1 for the incoming carry. Because we read node.next.val before that node is processed, we always see its original value, not a doubled one.

Example: 1→8→9 is 189. The head 1 is below 5, so no extra node. Node 1: 1*2 = 2, next is 8 (≥ 5) so add 1 → 3. Node 8: 16 % 10 = 6, next is 9 (≥ 5) so add 1 → 7. Node 9: 18 % 10 = 8, no next → 8. The result is 3→7→8 = 378.

Time: O(n) Space: O(1)