What is the brute force approach and complexity for Add Two Numbers II?

For each column from the right, walk from the head to reach that column's digits with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Add Two Numbers II?

Flip both lists so the ones digit is first, add from the heads, flip the inputs back with optimal time complexity O(N + M) and space complexity O(1).

How do you identify the pattern for Add Two Numbers II?

Look for key signals in the prompt: "digits, most significant first" indicates Column addition starts from the right, but the heads are on the left. Reverse the lists, or use stacks, so the right end becomes reachable.; "add two numbers" indicates The same idea as Add Two Numbers: a digit pair plus a carry, one column at a time.; "singly linked list" indicates We can't walk backwards, so the right-to-left order has to come from reversal or from a stack..

Add Two Numbers II

Medium·LeetCode #445 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given two numbers. Each one is stored as a linked list, with one digit per node. The most significant digit comes first, so the head holds the biggest place value.

Add the two numbers and return the sum as a new linked list, in the same format.

Leave both input lists exactly as they were when you return. Their values and their order must not change.

Input

l1 and l2, the heads of two singly linked lists of digits.

Output

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

Example 1

Input: l1 = [7, 2, 4, 3], l2 = [5, 6, 4]

Output: [7, 8, 0, 7]

7243 + 564 = 7807.

Example 2

Input: l1 = [0], l2 = [0]

Output: [0]

Zero plus zero is zero.

Example 3

Input: l1 = [9, 9], l2 = [1]

Output: [1, 0, 0]

99 + 1 = 100. The carry runs all the way to the front and adds a new digit.

Constraints

• Each list has between 1 and 100 nodes.
• 0 ≤ Node.val ≤ 9
• No leading zeros, except for the number 0 itself.
• Follow-up: can you do it without changing the input lists?

Pattern Recognition Clues

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

“digits, most significant first”

→ Column addition starts from the right, but the heads are on the left. Reverse the lists, or use stacks, so the right end becomes reachable.

“add two numbers”

→ The same idea as Add Two Numbers: a digit pair plus a carry, one column at a time.

“singly linked list”

→ We can't walk backwards, so the right-to-left order has to come from reversal or from a stack.

Approach Complexity Ladder

Brute Force — walk to each digit from the headO(N²)O(1)

For each column from the right, walk from the head to reach that column's digits

Better — two stacksO(N + M)O(N + M)

Push the digits of both numbers, then pop them: the top is the ones digit

Optimal — reverse both, add from the heads, reverse backO(N + M)O(1)

Flip both lists so the ones digit is first, add from the heads, flip the inputs back

Brute Force Intuition

Column addition starts at the ones digit. The lists can only be walked from the head, so for each column, walk from the head to the digit that sits in that column, add the two digits and the carry, and put the new digit in front of the answer. The idea is right, but every column walks the lists again from the start.

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