Add Two Numbers Represented as Linked List in DSA Go

Mental Model

We add two numbers digit by digit like in school, but each digit is a node in a linked list. We move through both lists at the same time, adding digits and carrying over if needed.

Analogy: Imagine adding two numbers written on two strips of paper, one digit per box, starting from the rightmost box. You add each pair of digits and carry over the extra to the next box on the left.

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

Dry Run Walkthrough

Input: list1: 2->4->3, list2: 5->6->4 (representing 342 + 465)

Goal: Add the two numbers and return the sum as a linked list in the same reversed order

Step 1: Add first nodes: 2 + 5 = 7, no carry

Result: 7 -> null

Why: Start adding from the least significant digit

Step 2: Add second nodes: 4 + 6 = 10, carry 1

Result: 7 -> 0 -> null

Why: Sum is 10, so digit is 0 and carry 1 to next

Step 3: Add third nodes plus carry: 3 + 4 + 1 = 8, no carry

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

Why: Add last digits and carry, no extra carry

Result:

7 -> 0 -> 8 -> null (represents 807)

Annotated Code

DSA Go

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 {
        sum := carry
        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }
        carry = sum / 10
        current.Next = &ListNode{Val: sum % 10}
        current = current.Next
    }
    return dummy.Next
}

func printList(node *ListNode) {
    for node != nil {
        fmt.Print(node.Val)
        if node.Next != nil {
            fmt.Print(" -> ")
        }
        node = node.Next
    }
    fmt.Println(" -> null")
}

func main() {
    // Create list1: 2 -> 4 -> 3
    l1 := &ListNode{2, &ListNode{4, &ListNode{3, nil}}}
    // Create list2: 5 -> 6 -> 4
    l2 := &ListNode{5, &ListNode{6, &ListNode{4, nil}}}

    result := addTwoNumbers(l1, l2)
    printList(result)
}

for l1 != nil || l2 != nil || carry != 0 {

continue adding while there are digits or carry left

sum := carry

start sum with carry from previous addition

if l1 != nil { sum += l1.Val; l1 = l1.Next }

add digit from first list and move forward

if l2 != nil { sum += l2.Val; l2 = l2.Next }

add digit from second list and move forward

carry = sum / 10

calculate carry for next digit

current.Next = &ListNode{Val: sum % 10}

create new node with current digit

current = current.Next

move current pointer to new node

Output

7 -> 0 -> 8 -> null

Complexity Analysis

Time: O(max(m, n)) because we traverse both lists once where m and n are their lengths

Space: O(max(m, n)) for the new linked list storing the sum digits

vs Alternative: Compared to converting lists to numbers and back, this method avoids large integer operations and handles very long numbers efficiently

Edge Cases

One list is empty

Returns the other list as the sum

DSA Go

for l1 != nil || l2 != nil || carry != 0 {

Sum produces an extra carry digit

Adds an extra node for the carry at the end

DSA Go

for l1 != nil || l2 != nil || carry != 0 {

Lists of different lengths

Continues adding remaining digits of longer list with carry

DSA Go

if l1 != nil { sum += l1.Val; l1 = l1.Next }

When to Use This Pattern

When you see two numbers stored as linked lists with digits in reverse order and need to add them, use the digit-by-digit addition pattern with carry to build the result list.

Common Mistakes

Mistake: Not handling the carry after the last nodes are processed
Fix: Include carry in the loop condition to add an extra node if carry remains

Mistake: Advancing pointers before adding their values
Fix: Add values first, then move pointers forward

Summary

Adds two numbers represented as reversed linked lists digit by digit with carry.

Use when adding large numbers stored as linked lists to avoid integer overflow.

The key is to add digits and carry simultaneously while traversing both lists.

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