LeetCode #2816 — MEDIUM

Double a Number Represented as a Linked List

Move from brute-force thinking to an efficient approach using linked list strategy.

The Problem

Problem Statement

You are given the head of a non-empty linked list representing a non-negative integer without leading zeroes.

Return the head of the linked list after doubling it.

Example 1:

Input: head = [1,8,9]
Output: [3,7,8]
Explanation: The figure above corresponds to the given linked list which represents the number 189. Hence, the returned linked list represents the number 189 * 2 = 378.

Example 2:

Input: head = [9,9,9]
Output: [1,9,9,8]
Explanation: The figure above corresponds to the given linked list which represents the number 999. Hence, the returned linked list reprersents the number 999 * 2 = 1998.

Constraints:

The number of nodes in the list is in the range [1, 10⁴]
0 <= Node.val <= 9
The input is generated such that the list represents a number that does not have leading zeros, except the number 0 itself.

Step 01

Brute Force Baseline

Problem summary: You are given the head of a non-empty linked list representing a non-negative integer without leading zeroes. Return the head of the linked list after doubling it.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Linked List · Math · Stack

Example 1

[1,8,9]

Example 2

[9,9,9]

Core Insight

What unlocks the optimal approach

Traverse the linked list from the least significant digit to the most significant digit and multiply each node's value by 2
Handle any carry-over digits that may arise during the doubling process.
If there is a carry-over digit on the most significant digit, create a new node with that value and point it to the start of the given linked list and return it.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #2816: Double a Number Represented as a Linked List
/**
 * Definition for singly-linked list.
 * public 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) {
        head = reverse(head);
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        int mul = 2, carry = 0;
        while (head != null) {
            int x = head.val * mul + carry;
            carry = x / 10;
            cur.next = new ListNode(x % 10);
            cur = cur.next;
            head = head.next;
        }
        if (carry > 0) {
            cur.next = new ListNode(carry);
        }
        return reverse(dummy.next);
    }

    private ListNode reverse(ListNode head) {
        ListNode dummy = new ListNode();
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = dummy.next;
            dummy.next = cur;
            cur = next;
        }
        return dummy.next;
    }
}

// Accepted solution for LeetCode #2816: Double a Number Represented as a Linked List
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func doubleIt(head *ListNode) *ListNode {
	head = reverse(head)
	dummy := &ListNode{}
	cur := dummy
	mul, carry := 2, 0
	for head != nil {
		x := head.Val*mul + carry
		carry = x / 10
		cur.Next = &ListNode{Val: x % 10}
		cur = cur.Next
		head = head.Next
	}
	if carry > 0 {
		cur.Next = &ListNode{Val: carry}
	}
	return reverse(dummy.Next)
}

func reverse(head *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = dummy.Next
		dummy.Next = cur
		cur = next
	}
	return dummy.Next
}

# Accepted solution for LeetCode #2816: Double a Number Represented as a Linked List
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(head):
            dummy = ListNode()
            cur = head
            while cur:
                next = cur.next
                cur.next = dummy.next
                dummy.next = cur
                cur = next
            return dummy.next

        head = reverse(head)
        dummy = cur = ListNode()
        mul, carry = 2, 0
        while head:
            x = head.val * mul + carry
            carry = x // 10
            cur.next = ListNode(x % 10)
            cur = cur.next
            head = head.next
        if carry:
            cur.next = ListNode(carry)
        return reverse(dummy.next)

// Accepted solution for LeetCode #2816: Double a Number Represented as a Linked List
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (java):
// // Accepted solution for LeetCode #2816: Double a Number Represented as a Linked List
// /**
//  * Definition for singly-linked list.
//  * public 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) {
//         head = reverse(head);
//         ListNode dummy = new ListNode();
//         ListNode cur = dummy;
//         int mul = 2, carry = 0;
//         while (head != null) {
//             int x = head.val * mul + carry;
//             carry = x / 10;
//             cur.next = new ListNode(x % 10);
//             cur = cur.next;
//             head = head.next;
//         }
//         if (carry > 0) {
//             cur.next = new ListNode(carry);
//         }
//         return reverse(dummy.next);
//     }
// 
//     private ListNode reverse(ListNode head) {
//         ListNode dummy = new ListNode();
//         ListNode cur = head;
//         while (cur != null) {
//             ListNode next = cur.next;
//             cur.next = dummy.next;
//             dummy.next = cur;
//             cur = next;
//         }
//         return dummy.next;
//     }
// }

// Accepted solution for LeetCode #2816: Double a Number Represented as a Linked List
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function doubleIt(head: ListNode | null): ListNode | null {
    head = reverse(head);
    const dummy = new ListNode();
    let cur = dummy;
    let mul = 2;
    let carry = 0;
    while (head) {
        const x = head.val * mul + carry;
        carry = Math.floor(x / 10);
        cur.next = new ListNode(x % 10);
        cur = cur.next;
        head = head.next;
    }
    if (carry) {
        cur.next = new ListNode(carry);
    }
    return reverse(dummy.next);
}

function reverse(head: ListNode | null): ListNode | null {
    const dummy = new ListNode();
    let cur = head;
    while (cur) {
        const next = cur.next;
        cur.next = dummy.next;
        dummy.next = cur;
        cur = next;
    }
    return dummy.next;
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(1)

Approach Breakdown

COPY TO ARRAY

O(n) time

O(n) space

Copy all n nodes into an array (O(n) time and space), then use array indexing for random access. Operations like reversal or middle-finding become trivial with indices, but the O(n) extra space defeats the purpose of using a linked list.

IN-PLACE POINTERS

O(n) time

O(1) space

Most linked list operations traverse the list once (O(n)) and re-wire pointers in-place (O(1) extra space). The brute force often copies nodes to an array to enable random access, costing O(n) space. In-place pointer manipulation eliminates that.

Shortcut: Traverse once + re-wire pointers → O(n) time, O(1) space. Dummy head nodes simplify edge cases.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Losing head/tail while rewiring

Wrong move: Pointer updates overwrite references before they are saved.

Usually fails on: List becomes disconnected mid-operation.

Fix: Store next pointers first and use a dummy head for safer joins.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.

Breaking monotonic invariant

Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.

Usually fails on: Indices point to blocked elements and outputs shift.

Fix: Pop while invariant is violated before pushing current element.