Double a Number Represented as a Linked List

LeetCode problem #2816

Language Selection

Choose your preferred programming language

Showing: Python

Problem Statement

You are given the head of a non-empty singly linked list where each node contains a single digit (0–9). The digits represent a non-negative integer in most-significant-digit-first order.

Return the head of a linked list representing twice the number.

Input / Output Format

Input: head — the head node of a singly linked list of digits (MSD first).
Output: head of a singly linked list representing 2 * number.

Constraints

The number of nodes is in the range [1, 10^4]
0 <= Node.val <= 9
The list represents a non-negative integer with no leading zeros except the number 0 itself.

Examples

Example 1

Input: 1 -> 8 -> 9
Represents 189
Output: 3 -> 7 -> 8
Represents 378
Explanation: 189 * 2 = 378

Example 2

Input: 9 -> 9 -> 9
Represents 999
Output: 1 -> 9 -> 9 -> 8
Represents 1998
Explanation: 999 * 2 = 1998 (carry creates a new leading node)

Example 3

Input: 0
Represents 0
Output: 0
Explanation: 0 * 2 = 0

Edge-case Example

Input: 5
Output: 1 -> 0
Explanation: 5 * 2 = 10 (new node due to carry)

Approach 1: Brute Force

Idea

Convert the linked list into a number-like representation, double it, then convert back.

Because the list length can be up to 10^4, we should not parse into built-in integer types (overflow in most languages). Instead:

Read digits into an array/string.
Perform grade-school multiplication by 2 from the end with carry.
Build a new linked list from the resulting digits.

This is “brute force” in the sense that we use extra storage for all digits and rebuild the list.

Algorithm

Traverse list, store digits in an array.
From right to left:
- x = digits[i] * 2 + carry
- resultDigit = x % 10, carry = x / 10
If carry remains, prepend it.
Build and return a new list from result digits.

Complexity

Time: O(n)
Space: O(n) extra (digits array + result list)

Code (Python)

from typing import Optional, List

class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next

class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None  # defensive; problem says non-empty

        digits: List[int] = []
        cur = head
        while cur:
            if cur.val < 0 or cur.val > 9:
                raise ValueError("Node value must be a digit 0..9")
            digits.append(cur.val)
            cur = cur.next

        carry = 0
        res: List[int] = []
        for i in range(len(digits) - 1, -1, -1):
            x = digits[i] * 2 + carry
            res.append(x % 10)
            carry = x // 10

        if carry:
            res.append(carry)

        res.reverse()

        dummy = ListNode(0)
        tail = dummy
        for d in res:
            tail.next = ListNode(d)
            tail = tail.next
        return dummy.next

Code (Java)

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode doubleIt(ListNode head) {
        if (head == null) return null; // defensive

        List<Integer> digits = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            if (cur.val < 0 || cur.val > 9) {
                throw new IllegalArgumentException("Node value must be 0..9");
            }
            digits.add(cur.val);
        }

        int carry = 0;
        List<Integer> resRev = new ArrayList<>();
        for (int i = digits.size() - 1; i >= 0; i--) {
            int x = digits.get(i) * 2 + carry;
            resRev.add(x % 10);
            carry = x / 10;
        }
        if (carry != 0) resRev.add(carry);

        // reverse into correct order and build list
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int i = resRev.size() - 1; i >= 0; i--) {
            tail.next = new ListNode(resRev.get(i));
            tail = tail.next;
        }
        return dummy.next;
    }
}

Code (Go)

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func doubleIt(head *ListNode) *ListNode {
	if head == nil {
		return nil // defensive
	}

	digits := make([]int, 0, 16)
	for cur := head; cur != nil; cur = cur.Next {
		if cur.Val < 0 || cur.Val > 9 {
			panic("node value must be a digit 0..9")
		}
		digits = append(digits, cur.Val)
	}

	carry := 0
	resRev := make([]int, 0, len(digits)+1)
	for i := len(digits) - 1; i >= 0; i-- {
		x := digits[i]*2 + carry
		resRev = append(resRev, x%10)
		carry = x / 10
	}
	if carry != 0 {
		resRev = append(resRev, carry)
	}

	dummy := &ListNode{}
	tail := dummy
	for i := len(resRev) - 1; i >= 0; i-- {
		tail.Next = &ListNode{Val: resRev[i]}
		tail = tail.Next
	}
	return dummy.Next
}

func main() {
	_ = fmt.Println
}

Code (JavaScript)

/**
 * Definition for singly-linked list.
 */
class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

var doubleIt = function(head) {
  if (head == null) return null; // defensive

  const digits = [];
  for (let cur = head; cur; cur = cur.next) {
    if (cur.val < 0 || cur.val > 9) {
      throw new Error("Node value must be a digit 0..9");
    }
    digits.push(cur.val);
  }

  let carry = 0;
  const resRev = [];
  for (let i = digits.length - 1; i >= 0; i--) {
    const x = digits[i] * 2 + carry;
    resRev.push(x % 10);
    carry = Math.floor(x / 10);
  }
  if (carry) resRev.push(carry);

  const dummy = new ListNode(0);
  let tail = dummy;
  for (let i = resRev.length - 1; i >= 0; i--) {
    tail.next = new ListNode(resRev[i]);
    tail = tail.next;
  }
  return dummy.next;
};

Code (C#)

using System;
using System.Collections.Generic;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode DoubleIt(ListNode head) {
        if (head == null) return null; // defensive

        var digits = new List<int>();
        for (var cur = head; cur != null; cur = cur.next) {
            if (cur.val < 0 || cur.val > 9)
                throw new ArgumentException("Node value must be a digit 0..9");
            digits.Add(cur.val);
        }

        int carry = 0;
        var resRev = new List<int>(digits.Count + 1);
        for (int i = digits.Count - 1; i >= 0; i--) {
            int x = digits[i] * 2 + carry;
            resRev.Add(x % 10);
            carry = x / 10;
        }
        if (carry != 0) resRev.Add(carry);

        var dummy = new ListNode(0);
        var tail = dummy;
        for (int i = resRev.Count - 1; i >= 0; i--) {
            tail.next = new ListNode(resRev[i]);
            tail = tail.next;
        }
        return dummy.next;
    }
}

Approach 2: Optimized Solution

Idea

Avoid storing all digits. We can process from least significant digit, but the list is MSB-first. Two common options:

Reverse the list, process with carry, reverse back (in-place).
Or use recursion/stack to simulate reverse traversal.

We’ll use reverse twice (iterative), which is simple, O(1) extra space.

Algorithm

Reverse the list.
Traverse nodes:
- sum = node.val * 2 + carry
- update node.val = sum % 10, carry = sum / 10
If carry remains after traversal, append a new node with carry.
Reverse the list back and return head.

Complexity

Time: O(n)
Space: O(1) extra (not counting output nodes; only possibly one extra node for carry)

Code (Python)

from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next

class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None  # defensive

        def reverse(node: ListNode) -> ListNode:
            prev = None
            cur = node
            while cur:
                nxt = cur.next
                cur.next = prev
                prev = cur
                cur = nxt
            return prev

        head = reverse(head)

        carry = 0
        cur = head
        prev = None
        while cur:
            if cur.val < 0 or cur.val > 9:
                raise ValueError("Node value must be a digit 0..9")
            x = cur.val * 2 + carry
            cur.val = x % 10
            carry = x // 10
            prev = cur
            cur = cur.next

        if carry:
            prev.next = ListNode(carry)

        head = reverse(head)
        return head

Code (Java)

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode doubleIt(ListNode head) {
        if (head == null) return null; // defensive

        head = reverse(head);

        int carry = 0;
        ListNode cur = head;
        ListNode prev = null;

        while (cur != null) {
            if (cur.val < 0 || cur.val > 9) {
                throw new IllegalArgumentException("Node value must be 0..9");
            }
            int x = cur.val * 2 + carry;
            cur.val = x % 10;
            carry = x / 10;

            prev = cur;
            cur = cur.next;
        }

        if (carry != 0) {
            prev.next = new ListNode(carry);
        }

        return reverse(head);
    }

    private ListNode reverse(ListNode node) {
        ListNode prev = null, cur = node;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
}

Code (Go)

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func doubleIt(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}

	head = reverse(head)

	carry := 0
	cur := head
	var prev *ListNode

	for cur != nil {
		if cur.Val < 0 || cur.Val > 9 {
			panic("node value must be a digit 0..9")
		}
		x := cur.Val*2 + carry
		cur.Val = x % 10
		carry = x / 10

		prev = cur
		cur = cur.Next
	}

	if carry != 0 {
		prev.Next = &ListNode{Val: carry}
	}

	return reverse(head)
}

func reverse(node *ListNode) *ListNode {
	var prev *ListNode
	cur := node
	for cur != nil {
		nxt := cur.Next
		cur.Next = prev
		prev = cur
		cur = nxt
	}
	return prev
}

Code (JavaScript)

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function reverse(node) {
  let prev = null, cur = node;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

var doubleIt = function(head) {
  if (head == null) return null;

  head = reverse(head);

  let carry = 0;
  let cur = head;
  let prev = null;

  while (cur) {
    if (cur.val < 0 || cur.val > 9) {
      throw new Error("Node value must be a digit 0..9");
    }
    const x = cur.val * 2 + carry;
    cur.val = x % 10;
    carry = Math.floor(x / 10);

    prev = cur;
    cur = cur.next;
  }

  if (carry) {
    prev.next = new ListNode(carry);
  }

  return reverse(head);
};

Code (C#)

using System;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode DoubleIt(ListNode head) {
        if (head == null) return null;

        head = Reverse(head);

        int carry = 0;
        var cur = head;
        ListNode prev = null;

        while (cur != null) {
            if (cur.val < 0 || cur.val > 9)
                throw new ArgumentException("Node value must be a digit 0..9");

            int x = cur.val * 2 + carry;
            cur.val = x % 10;
            carry = x / 10;

            prev = cur;
            cur = cur.next;
        }

        if (carry != 0) {
            prev.next = new ListNode(carry);
        }

        return Reverse(head);
    }

    private ListNode Reverse(ListNode node) {
        ListNode prev = null, cur = node;
        while (cur != null) {
            var nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }
}

Key Insights

Doubling is easiest from least significant digit because of carry propagation.
Since the list is MSB-first, reversing (or recursion/stack) is the standard trick to process from the end.
Only one extra node is ever needed (when the final carry is non-zero).

Edge Cases

Single node with value 0 → stays 0
Single digit that produces carry: 5 -> 10, 9 -> 18
All 9s: 9->9->...->9 creates a new leading node
Very long list (10^4 nodes): avoid integer parsing; ensure O(n) operations
Defensive: node values outside 0..9 (shouldn’t happen on LeetCode, but handled)

Test Cases

Python Test Code

def build_list(nums):
    dummy = ListNode(0)
    cur = dummy
    for x in nums:
        cur.next = ListNode(x)
        cur = cur.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def run_tests():
    s = Solution()

    tests = [
        ([1,8,9], [3,7,8]),
        ([9,9,9], [1,9,9,8]),
        ([0], [0]),
        ([5], [1,0]),
        ([4,9,9], [9,9,8]),
    ]

    for inp, exp in tests:
        head = build_list(inp)
        got = to_list(s.doubleIt(head))
        assert got == exp, (inp, got, exp)

run_tests()
print("OK")

Java Test Code

import java.util.*;

public class Main {
    static ListNode build(int[] a) {
        ListNode dummy = new ListNode(0), tail = dummy;
        for (int x : a) {
            tail.next = new ListNode(x);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) out.add(cur.val);
        return out;
    }

    static void assertEq(List<Integer> got, int[] exp) {
        if (got.size() != exp.length) throw new AssertionError("Length mismatch");
        for (int i = 0; i < exp.length; i++) {
            if (got.get(i) != exp[i]) throw new AssertionError("Mismatch at " + i);
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();

        int[][] inputs = {
            {1,8,9},
            {9,9,9},
            {0},
            {5},
            {4,9,9}
        };
        int[][] expects = {
            {3,7,8},
            {1,9,9,8},
            {0},
            {1,0},
            {9,9,8}
        };

        for (int i = 0; i < inputs.length; i++) {
            ListNode head = build(inputs[i]);
            ListNode ans = s.doubleIt(head);
            assertEq(toList(ans), expects[i]);
        }
        System.out.println("OK");
    }
}

Go Test Code

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func build(a []int) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for _, x := range a {
		tail.Next = &ListNode{Val: x}
		tail = tail.Next
	}
	return dummy.Next
}

func toSlice(head *ListNode) []int {
	out := []int{}
	for cur := head; cur != nil; cur = cur.Next {
		out = append(out, cur.Val)
	}
	return out
}

func equal(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

// Plug in either approach's doubleIt implementation here.
func reverse(node *ListNode) *ListNode {
	var prev *ListNode
	cur := node
	for cur != nil {
		nxt := cur.Next
		cur.Next = prev
		prev = cur
		cur = nxt
	}
	return prev
}

func doubleIt(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	head = reverse(head)
	carry := 0
	cur := head
	var prev *ListNode
	for cur != nil {
		x := cur.Val*2 + carry
		cur.Val = x % 10
		carry = x / 10
		prev = cur
		cur = cur.Next
	}
	if carry != 0 {
		prev.Next = &ListNode{Val: carry}
	}
	return reverse(head)
}

func main() {
	tests := []struct {
		in  []int
		exp []int
	}{
		{[]int{1, 8, 9}, []int{3, 7, 8}},
		{[]int{9, 9, 9}, []int{1, 9, 9, 8}},
		{[]int{0}, []int{0}},
		{[]int{5}, []int{1, 0}},
		{[]int{4, 9, 9}, []int{9, 9, 8}},
	}

	for _, tc := range tests {
		got := toSlice(doubleIt(build(tc.in)))
		if !equal(got, tc.exp) {
			panic(fmt.Sprintf("in=%v got=%v exp=%v", tc.in, got, tc.exp))
		}
	}
	fmt.Println("OK")
}

Common Mistakes

Trying to convert the whole list into an int/long (overflow for large lists).
Forgetting to handle the final carry (e.g., 999 -> 1998).
Modifying pointers incorrectly when reversing (losing the list).
Building the result backwards (mixing MSB/LSB order).
Not considering input 0.

Interview Tips

Start by stating: “This is big-integer doubling with digits in a linked list; carry flows from the tail.”
Mention two strategies:
- Extra space (array/stack) to process from end.
- In-place reverse, process, reverse back (optimal space).
Emphasize complexity: O(n) time; optimized is O(1) extra space.
Walk through a carry-heavy case (9->9->9) to show correctness.
If asked about recursion: note recursion depth up to 10^4 may risk stack overflow in some languages; iterative reverse is safer.