Add Two Numbers Represented as Linked List in DSA Go - Deep Dive

Overview - Add Two Numbers Represented as Linked List

What is it?

This topic is about adding two numbers where each number is stored as a linked list. Each node in the list holds a single digit, and the digits are stored in reverse order, meaning the first node is the ones place. The goal is to add these two numbers and return the sum as a new linked list in the same reversed format.

Why it matters

Without this concept, handling very large numbers that don't fit in standard data types would be difficult. It allows us to perform addition digit by digit, just like how we add numbers by hand. This is useful in systems that process numbers too big for normal variables or when numbers come in parts, like in streaming data.

Where it fits

Before this, you should understand what linked lists are and how to traverse them. After this, you can learn about other linked list operations like subtraction, multiplication, or more complex data structures like trees and graphs.

Mental Model

Core Idea

Adding two numbers as linked lists is like adding digits one by one from right to left, carrying over extra values just like manual addition.

Think of it like...

Imagine adding two long numbers written on paper from right to left, carrying over when the sum of digits is more than 9, but instead of paper, each digit is a bead on a string.

List1: 2 -> 4 -> 3 -> null
List2: 5 -> 6 -> 4 -> null

Add digits:
2 + 5 = 7 (no carry)
4 + 6 = 10 (carry 1)
3 + 4 + 1 = 8 (no carry)

Result: 7 -> 0 -> 8 -> null

Build-Up - 7 Steps

1

Foundation

Understanding Linked List Structure

Concept: Learn what a linked list is and how nodes connect to form a sequence.

A linked list is a chain of nodes. Each node holds a value and a pointer to the next node. For example, a list with digits 2, 4, 3 looks like: Node(2) -> Node(4) -> Node(3) -> null. The 'null' means the end of the list.

Result

You can represent a number as a linked list where each node is a digit.

Understanding the linked list structure is essential because the addition process depends on traversing these nodes one by one.

2

Foundation

Representing Numbers in Reverse Order

Concept: Digits are stored in reverse order to simplify addition from least significant digit.

The number 342 is stored as 2 -> 4 -> 3 -> null. This way, the first node is the ones place, the second is tens, and so on. This matches how we add numbers starting from the rightmost digit.

Result

You can easily add two numbers by starting from the head of each list.

Storing digits in reverse order aligns with the natural addition process, making the algorithm simpler.

3

Intermediate

Digit-by-Digit Addition with Carry

🤔Before reading on: do you think you need to process the entire list before adding, or can you add as you go? Commit to your answer.

Concept: Add corresponding digits from both lists and keep track of carry for sums over 9.

Start from the heads of both lists. Add their digits plus any carry from previous addition. If sum >= 10, carry 1 to next digit. Create a new node for the sum's digit (sum % 10). Move to next nodes and repeat until both lists and carry are done.

Result

A new linked list representing the sum digit by digit.

Adding as you go avoids extra passes and uses the carry concept just like manual addition.

4

Intermediate

Handling Different Length Lists

🤔If one list is longer than the other, do you think you stop early or continue adding? Commit to your answer.

Concept: Continue addition even if one list ends, treating missing digits as zero.

If one list is shorter, treat missing nodes as zero. Continue adding digits and carry until both lists are fully processed and no carry remains.

Result

Correct sum even when lists have different lengths.

Handling different lengths ensures the algorithm works for all inputs, not just equal-sized numbers.

5

Intermediate

Creating the Result Linked List

🤔Do you think the result list is built by modifying input lists or creating new nodes? Commit to your answer.

Concept: Build a new linked list to store the sum digits without changing input lists.

Create a dummy head node to start the result list. For each sum digit, create a new node and link it to the result list. This keeps inputs unchanged and makes code cleaner.

Result

A new linked list representing the sum without side effects.

Creating a new list avoids bugs and preserves original data, which is important in many applications.

6

Advanced

Implementing the Addition in Go

🤔Before reading code: do you think the carry should be handled inside or outside the loop? Commit to your answer.

Concept: Write complete Go code to add two linked lists digit by digit with carry.

package main import "fmt" type ListNode struct { Val int Next *ListNode } func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { dummy := &ListNode{} current := dummy carry := 0 for l1 != nil || l2 != nil || carry != 0 { var x, y int if l1 != nil { x = l1.Val l1 = l1.Next } if l2 != nil { y = l2.Val l2 = l2.Next } sum := x + y + carry carry = sum / 10 current.Next = &ListNode{Val: sum % 10} current = current.Next } return dummy.Next } func printList(node *ListNode) { for node != nil { fmt.Printf("%d", node.Val) if node.Next != nil { fmt.Printf(" -> ") } node = node.Next } fmt.Println(" -> null") } func main() { l1 := &ListNode{2, &ListNode{4, &ListNode{3, nil}}} l2 := &ListNode{5, &ListNode{6, &ListNode{4, nil}}} result := addTwoNumbers(l1, l2) printList(result) }

Result

7 -> 0 -> 8 -> null

Seeing the full code ties all concepts together and shows how carry and node creation work in practice.

7

Expert

Optimizing for Memory and Edge Cases

🤔Do you think reusing nodes from input lists is safe or risky? Commit to your answer.

Concept: Explore memory optimization by reusing nodes and handling edge cases like empty lists or large carries.

In some cases, you can reuse nodes from input lists to save memory, but this risks modifying inputs unexpectedly. Also, handle cases where one or both lists are empty, or the final carry creates a new node. Testing these edge cases ensures robustness.

Result

Efficient and safe addition handling all input variations.

Knowing when to reuse nodes and how to handle edge cases prevents bugs and improves performance in real systems.

Under the Hood

The algorithm traverses both linked lists simultaneously, adding corresponding digits and a carry value. It uses integer division and modulo to separate the carry and the digit to store. Memory is allocated for new nodes to build the result list. The process continues until all digits and carry are processed.

Why designed this way?

Storing digits in reverse order and adding from head to tail mimics manual addition, simplifying carry handling. Creating a new list avoids side effects on inputs. This design balances simplicity, correctness, and efficiency.

┌─────────────┐     ┌─────────────┐     ┌─────────────┐
│ List1 Node  │ --> │ List1 Node  │ --> │ List1 Node  │ --> null
│   (Digit)   │     │   (Digit)   │     │   (Digit)   │
└─────────────┘     └─────────────┘     └─────────────┘
       │                   │                   │
       ▼                   ▼                   ▼
┌─────────────┐     ┌─────────────┐     ┌─────────────┐
│ List2 Node  │ --> │ List2 Node  │ --> │ List2 Node  │ --> null
│   (Digit)   │     │   (Digit)   │     │   (Digit)   │
└─────────────┘     └─────────────┘     └─────────────┘
       │                   │                   │
       ▼                   ▼                   ▼
  Add digits + carry -> Create new node -> Link to result list

Repeat until all nodes and carry processed

Myth Busters - 4 Common Misconceptions

Quick: Do you think you can add the numbers by just concatenating the lists? Commit yes or no.

Common Belief: You can add two numbers by just joining their linked lists end to end.

Reality: Concatenating lists does not add their values; it just links them. Addition requires digit-wise sum and carry handling.

Why it matters: Mistaking concatenation for addition leads to wrong results and bugs in programs handling large numbers.

Quick: Do you think the carry can be ignored if the sum digit is less than 10? Commit yes or no.

Common Belief: Carry only matters if the sum digit is exactly 10, otherwise it can be ignored.

Reality: Carry must be added whenever the sum is 10 or more, not just exactly 10.

Why it matters: Ignoring carry in sums over 10 causes incorrect final sums and subtle bugs.

Quick: Do you think the input lists can be modified safely during addition? Commit yes or no.

Common Belief: It's safe to change the input linked lists while adding to save memory.

Reality: Modifying input lists can cause unexpected side effects if those lists are used elsewhere.

Why it matters: Changing inputs breaks data integrity and can cause hard-to-find bugs in larger systems.

Quick: Do you think the result list must be the same length as the longer input list? Commit yes or no.

Common Belief: The result list length is always equal to the longer input list length.

Reality: The result list can be longer by one node if there is a final carry after the last digits.

Why it matters: Not accounting for the extra carry node leads to missing digits in the sum.

Expert Zone

1

Reusing nodes from input lists can save memory but requires careful management to avoid side effects.

2

Handling carry as a separate variable outside the loop condition simplifies code and prevents off-by-one errors.

3

The dummy head node pattern is a subtle but powerful technique to simplify linked list construction and avoid special cases.

When NOT to use

This approach is not suitable when digits are stored in forward order (most significant digit first); in that case, you need to reverse lists first or use recursion. For extremely large numbers, specialized big integer libraries or arrays might be more efficient.

Production Patterns

In production, this pattern is used in financial software to handle arbitrary precision arithmetic, in blockchain systems for large number calculations, and in coding interviews to test understanding of linked lists and arithmetic operations.

Connections

Big Integer Arithmetic

Builds-on

Understanding addition with linked lists helps grasp how big integer libraries perform arithmetic on numbers larger than built-in types.

Manual Addition Algorithm

Same pattern

The linked list addition directly models the manual addition process, reinforcing the connection between algorithms and everyday math.

Data Streaming

Builds-on

Adding numbers digit by digit as streams arrive is similar to this linked list addition, showing how algorithms adapt to incremental data.

Common Pitfalls

#1 Stopping addition when one list ends, ignoring remaining digits in the longer list.

Wrong approach:

for l1 != nil && l2 != nil {
sum = l1.Val + l2.Val + carry
// process sum
l1 = l1.Next
l2 = l2.Next
}

Correct approach:

for l1 != nil || l2 != nil || carry != 0 {
var x, y int
if l1 != nil {
x = l1.Val
l1 = l1.Next
}
if l2 != nil {
y = l2.Val
l2 = l2.Next
}
sum = x + y + carry
// process sum
}

Root cause:

Misunderstanding that both lists may have different lengths and carry may still exist after one ends.

#2 Modifying input lists to store result digits, causing side effects.

Wrong approach:

l1.Val = (l1.Val + l2.Val + carry) % 10
carry = (l1.Val + l2.Val + carry) / 10
// returning l1 as result

Correct approach:

Create new nodes for result list without changing l1 or l2 values.

Root cause:

Trying to save memory without considering data integrity and reuse consequences.

#3 Ignoring final carry after processing all nodes.

Wrong approach:

for l1 != nil || l2 != nil {
// add digits
}
// no check for carry after loop

Correct approach:

for l1 != nil || l2 != nil || carry != 0 {
// add digits including carry
}

Root cause:

Not realizing carry can create an extra digit in the result.

Key Takeaways

Adding two numbers as linked lists mimics manual addition by processing digits from least significant to most with carry.

Storing digits in reverse order simplifies addition by aligning list heads with the ones place.

Handling different list lengths and carry correctly ensures the algorithm works for all inputs.

Creating a new linked list for the result preserves input data and avoids side effects.

Using a dummy head node and careful loop conditions makes the implementation clean and bug-free.

Practice

1. What does the problem "Add Two Numbers Represented as Linked List" ask you to do?

easy

A. Reverse the digits of a number stored in a linked list.

B. Multiply two numbers stored as linked lists and return the product as a linked list.

C. Add two numbers where each digit is stored in a node of a linked list, and return the sum as a linked list.

D. Find the maximum digit in a linked list representing a number.

Solution

1. Step 1: Understand the problem statement and identify the expected output

   The problem requires adding two numbers where each number is represented by a linked list, with each node holding a single digit. The sum should also be returned as a linked list, where each node contains a digit of the result.

2. Final Answer:

   Add two numbers represented as linked lists and return their sum as a linked list -> Option C

3. Quick Check:

   Adding digits node by node = Add two numbers where each digit is stored in a node of a linked list, and return the sum as a linked list. [OK]

Hint: Focus on adding digit by digit with carry [OK]

Common Mistakes:

• Confusing addition with multiplication
• Ignoring carry over between digits
• Returning a number instead of a linked list

2. Which of the following Go code snippets correctly defines a node for a singly linked list used to represent a digit in the "Add Two Numbers Represented as Linked List" problem?

easy

A. type ListNode struct { Val int; Next *ListNode }

B. type ListNode struct { Value string; Next ListNode }

C. type Node struct { Val int; Next int }

D. type ListNode struct { Val int; Next ListNode }

Solution

1. Step 1: Check struct field types and verify pointer usage

   The node should hold an integer value and a pointer to the next node, so Val is int and Next is *ListNode. Next must be a pointer to ListNode to allow linking nodes dynamically.

2. Final Answer:

   type ListNode struct { Val int; Next *ListNode } -> Option A

3. Quick Check:

   Pointer to next node = type ListNode struct { Val int; Next *ListNode } [OK]

Hint: Use *ListNode for next pointer in Go structs [OK]

Common Mistakes:

• Using value type instead of pointer for Next
• Using wrong field types like string for digits
• Missing semicolons or commas in struct

3. What will be the output linked list after adding the two numbers represented by these linked lists? List 1: 2 -> 4 -> 3 -> null (represents 342) List 2: 5 -> 6 -> 4 -> null (represents 465) Use the standard addition approach digit by digit with carry.

medium

A. 7 -> 0 -> 8 -> null

B. 8 -> 0 -> 7 -> null

C. 7 -> 10 -> 7 -> null

D. 7 -> 1 -> 8 -> null

Solution

1. Step 1: Add digits from head nodes with carry and form the result linked list

   2 + 5 = 7, carry 0; next digits 4 + 6 = 10, store 0 carry 1; next digits 3 + 4 + 1 = 8. The result digits are 7 -> 0 -> 8 representing 807.

2. Final Answer:

   7 -> 0 -> 8 -> null -> Option A

3. Quick Check:

   342 + 465 = 807 = 7->0->8 [OK]

Hint: Add digits with carry, store remainder as node value [OK]

Common Mistakes:

• Not carrying over when sum >= 10
• Adding digits in wrong order
• Confusing node values with actual number order

4. Consider this Go function snippet to add two numbers represented as linked lists. What is the bug? func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { carry := 0 dummy := &ListNode{} current := dummy for l1 != nil && l2 != nil { sum := l1.Val + l2.Val + carry carry = sum / 10 current.Next = &ListNode{Val: sum % 10} current = current.Next l1 = l1.Next l2 = l2.Next } return dummy.Next }

medium

A. The dummy node is not initialized properly.

B. Carry is not calculated correctly after sum.

C. The function does not return the correct node.

D. The loop stops when either list ends, missing remaining nodes in longer list.

Solution

1. Step 1: Analyze loop condition and identify missing processing

   The loop runs only while both l1 and l2 are not nil, so it stops if one list is longer. Remaining nodes in the longer list and any carry after loop are not handled, causing incorrect results.

2. Final Answer:

   The loop stops when either list ends, missing remaining nodes in longer list -> Option D

3. Quick Check:

   Loop condition misses longer list nodes = The loop stops when either list ends, missing remaining nodes in longer list. [OK]

Hint: Use OR condition to continue until both lists and carry are done [OK]

Common Mistakes:

• Using AND instead of OR in loop condition
• Ignoring leftover carry after loop
• Not linking remaining nodes after loop

5. You have two linked lists representing numbers in reverse order: List 1: 9 -> 9 -> 9 -> 9 -> null (represents 9999) List 2: 1 -> null (represents 1) What will be the resulting linked list after adding these two numbers?

hard

A. 0 -> 0 -> 0 -> 0 -> null

B. 0 -> 0 -> 0 -> 0 -> 1 -> null

C. 1 -> 0 -> 0 -> 0 -> 0 -> null

D. 9 -> 9 -> 9 -> 10 -> null

Solution

1. Step 1: Add digits with carry step-by-step and add final carry as new node

   9+1=10, store 0 carry 1; next 9+0+1=10, store 0 carry 1; repeat for all 9s, each time store 0 carry 1. After last 9, carry is 1, so add a new node with value 1 at the end.

2. Final Answer:

   0 -> 0 -> 0 -> 0 -> 1 -> null -> Option B

3. Quick Check:

   9999 + 1 = 10000 = 0->0->0->0->1 [OK]

Hint: Remember to add carry node if leftover after last digit [OK]

Common Mistakes:

• Not adding extra node for leftover carry
• Stopping addition too early
• Misplacing the carry node in the list