What is the brute force approach and complexity for Double a Number Represented as a Linked List?

Copy the digits into an array, double from the last one, build the answer from the front with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Double a Number Represented as a Linked List?

Flip the list, double each digit with the carry, add a node if a carry is left, flip back with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Double a Number Represented as a Linked List?

Look for key signals in the prompt: "double a number" indicates Each digit doubles, and gets the carry from the digit on its right. That is column arithmetic from the ones place.; "linked list of digits" indicates The most significant digit comes first, so the carry runs against the list. Reverse the list first.; "carry left at the end" indicates A carry after the last digit becomes a new head node. It is easy to forget..

Double a Number Represented as a Linked List

Medium·LeetCode #2816 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

You are given the head of a linked list that stores a non-negative whole number. Each node holds one digit, and the most significant digit comes first.

Return the head of a new linked list that stores the number multiplied by 2, in the same format.

Input

head, the first node of a singly linked list of digits. It is never empty.

Output

The head of a linked list holding the doubled number, most significant digit first.

Example 1

Input: head = [1, 8, 9]

Output: [3, 7, 8]

189 × 2 = 378.

Example 2

Input: head = [9, 9, 9]

Output: [1, 9, 9, 8]

999 × 2 = 1998. The carry out of the first digit needs a brand new leading digit.

Example 3

Input: head = [0]

Output: [0]

0 × 2 = 0.

Constraints

• The list has between 1 and 10^4 nodes.
• 0 ≤ Node.val ≤ 9
• No leading zeros, except for the number 0 itself.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“double a number”

→ Each digit doubles, and gets the carry from the digit on its right. That is column arithmetic from the ones place.

“linked list of digits”

→ The most significant digit comes first, so the carry runs against the list. Reverse the list first.

“carry left at the end”

→ A carry after the last digit becomes a new head node. It is easy to forget.

Approach Complexity Ladder

Brute Force — copy digits to an array, double from the endO(N)O(N)

Copy the digits into an array, double from the last one, build the answer from the front

Optimal — reverse, double with carry, reverse backO(N)O(1)

Flip the list, double each digit with the carry, add a node if a carry is left, flip back

Brute Force Intuition

An array can be read from the last index, which is the ones digit. Copy the digits into a vector, then double from the end to the start, carrying as we go. Each new digit goes in front of the answer. A carry left at the end adds one more digit at the front. The answer is right, but every digit gets copied.

Recognition rule for this sub-pattern:

Walk once, pointing each node back to the previous one.

Remember this · Linked List — Reversal

Trigger

Reverse whole / part / every k nodes, reorder, palindrome check, numbers stored as lists.

Think

Which piece do I reverse, and which nodes must I remember to reconnect afterwards?

Key question

Before reversing, who is the node just before the piece and who is just after?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Reversal translate into production architectures and low-level memory mechanics.

LLD Architecture