Add Two Numbers Represented as Linked List in DSA Rust - Execution Trace

Concept Flow - Add Two Numbers Represented as Linked List

Start at head of List1

↓

Add digits + carry

↓

Create new node with sum % 10

↓

Move to next nodes in both lists

↓

Carry = sum / 10

↓

Repeat until both lists and carry are empty

↓

Return head of result list

We add digits from two linked lists node by node, including carry, creating a new list for the sum.

Execution Sample

DSA Rust

fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut carry = 0;
    let mut p1 = l1;
    let mut p2 = l2;
    let mut dummy = Box::new(ListNode::new(0));
    let mut current = &mut dummy;
    while p1.is_some() || p2.is_some() || carry != 0 {
        let sum = p1.as_ref().map_or(0, |n| n.val) + p2.as_ref().map_or(0, |n| n.val) + carry;
        carry = sum / 10;
        current.next = Some(Box::new(ListNode::new(sum % 10)));
        current = current.next.as_mut().unwrap();
        p1 = p1.and_then(|n| n.next);
        p2 = p2.and_then(|n| n.next);
    }
    dummy.next
}

This code adds two numbers represented by linked lists digit by digit, handling carry, and returns the sum as a linked list.

Execution Table

Step	Operation	Digit from List1	Digit from List2	Carry Before	Sum	Carry After	New Node Value	Result List Visual
1	Add first digits	2	5	0	7	0	7	7 -> null
2	Add second digits	4	6	0	10	1	0	7 -> 0 -> null
3	Add third digits	3	4	1	8	0	8	7 -> 0 -> 8 -> null
4	No more digits, carry 0	0	0	0	0	0	-	7 -> 0 -> 8 -> null

💡 Both lists are fully traversed and carry is 0, so addition ends.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
p1	Node(2)	Node(4)	Node(3)	None	None
p2	Node(5)	Node(6)	Node(4)	None	None
carry	0	0	1	0	0
current Node	dummy(0)	Node(7)	Node(0)	Node(8)	Node(8)
Result List	empty	7 -> null	7 -> 0 -> null	7 -> 0 -> 8 -> null	7 -> 0 -> 8 -> null

Key Moments - 3 Insights

Why do we continue the loop when both lists are empty but carry is not zero?

Because carry can add an extra digit to the result. For example, after adding last digits, carry might be 1, so we must create a new node with that carry. See step 3 and 4 in execution_table.

Why do we use sum % 10 for the new node value?

Because each node stores a single digit (0-9). sum % 10 extracts the last digit of the sum to store in the node. Carry is sum / 10 for the next addition. See 'New Node Value' column in execution_table.

What happens if one list is longer than the other?

We treat missing digits as 0 using map_or(0, ...). So addition continues with the longer list's digits plus carry. This is why p1 and p2 can be None independently.

Visual Quiz - 3 Questions

Look at the execution_table, what is the carry after step 2?

A 0

B 2

C 1

D None

💡 Hint

Check the 'Carry After' column in row for step 2 in execution_table.

At which step does the result list first contain three nodes?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the 'Result List Visual' column in execution_table to see when three nodes appear.

If the first list had an extra digit 1 after 3, what would happen to the carry after step 3?

A Carry would be 0

B Carry would be 1

C Carry would be 2

D Carry would be unchanged

💡 Hint

Consider how adding an extra digit affects sum and carry in the loop, referencing variable_tracker and execution_table.

Concept Snapshot

Add digits from two linked lists node by node.
Use carry to handle sums > 9.
Create new nodes with sum % 10.
Continue until both lists and carry are empty.
Return new list head (skip dummy).
Handles different length lists gracefully.

Full Transcript

This concept adds two numbers represented as linked lists. Each node holds one digit. We start from the head of both lists, add digits plus carry, create a new node with the last digit of the sum, and update carry for the next step. We move to the next nodes in both lists and repeat until no digits or carry remain. The result is a new linked list representing the sum. The execution table shows step-by-step addition, carry updates, and the growing result list. Variable tracker shows pointer and carry changes. Key moments clarify why carry is important after lists end, why sum % 10 is used, and how different length lists are handled. The visual quiz tests understanding of carry, list length, and effect of extra digits. The snapshot summarizes the process simply.

Practice

1. What does the problem "Add Two Numbers Represented as Linked List" typically involve?

easy

A. Sorting two linked lists in ascending order

B. Adding two numbers where each digit is stored in a node of a linked list

C. Merging two linked lists into one

D. Finding the middle node of a linked list

Solution

1. Step 1: Understand the problem context

   The problem involves two linked lists where each node contains a single digit of a number, stored in reverse order.

2. Step 2: Identify the required operation

   We need to add these two numbers digit by digit, handling carry, and return the sum as a linked list.

3. Final Answer:

   Adding two numbers where each digit is stored in a node of a linked list -> Option B

4. Quick Check:

   Adding digits node-wise = Adding two numbers where each digit is stored in a node of a linked list [OK]

Hint: Think of adding digit by digit like elementary school addition [OK]

Common Mistakes:

• Confusing addition with merging or sorting
• Ignoring the carry between digits
• Assuming digits are stored in forward order

2. Which Rust code snippet correctly defines a singly linked list node for this problem?

easy

A. struct ListNode { val: i32, next: &ListNode }

B. struct ListNode { val: i32, next: ListNode }

C. struct ListNode { val: i32, next: Option }

D. struct ListNode { val: i32, next: Box<ListNode> }

Solution

1. Step 1: Recall Rust linked list node structure

   Each node holds a value and an optional pointer to the next node using Box wrapped in Option for possible None.

2. Step 2: Check each option

   struct ListNode { val: i32, next: Option } uses Option which is correct. struct ListNode { val: i32, next: ListNode } and D lack Option, causing infinite size. struct ListNode { val: i32, next: &ListNode } uses reference which is invalid for ownership.

3. Final Answer:

   struct ListNode { val: i32, next: Option } -> Option C

4. Quick Check:

   Use Option for linked list nodes in Rust [OK]

Hint: Use Option for next pointer in Rust linked lists [OK]

Common Mistakes:

• Using direct ListNode type for next causing infinite size
• Using references without lifetime annotations
• Omitting Option causing no None termination

3. What is the output linked list when adding (2 -> 4 -> 3) and (5 -> 6 -> 4) representing numbers 342 and 465 respectively?

medium

A. 7 -> 1 -> 8

B. 8 -> 0 -> 7

C. 7 -> 10 -> 7

D. 7 -> 0 -> 8

Solution

1. Step 1: Add digits with carry

   2+5=7 (carry 0), 4+6=10 (carry 1), 3+4+1=8 (carry 0)

2. Step 2: Form the resulting linked list

   Digits are 7 -> 0 -> 8 representing 807 in reverse order.

3. Final Answer:

   7 -> 0 -> 8 -> Option D

4. Quick Check:

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

Hint: Add digits and carry from left to right in linked list order [OK]

Common Mistakes:

• Not carrying over when sum >= 10
• Mixing digit order in output
• Adding digits without carry

4. Identify the bug in this Rust code snippet for adding two linked lists:

while l1.is_some() || l2.is_some() {
    let sum = l1.unwrap().val + l2.unwrap().val + carry;
    carry = sum / 10;
    let node = ListNode::new(sum % 10);
    // ...
}

medium

A. Calling unwrap() without checking if Option is Some causes panic

B. Carry is not updated correctly

C. ListNode::new does not create a node

D. Loop condition should use && instead of ||

Solution

1. Step 1: Analyze unwrap usage

   unwrap() on Option without checking Some causes panic if None occurs.

2. Step 2: Check loop condition and unwrap safety

   Loop runs while either list is Some, but unwrap is called on both without checking, causing runtime error.

3. Final Answer:

   Calling unwrap() without checking if Option is Some causes panic -> Option A

4. Quick Check:

   Always check Option before unwrap to avoid panic [OK]

Hint: Check Option is Some before unwrap to prevent panic [OK]

Common Mistakes:

• Assuming both lists have same length without checks
• Ignoring Option safety causing runtime panic
• Incorrect loop condition logic

5. Given two linked lists representing numbers in reverse order, how would you handle adding them if one list is longer than the other?

hard

A. Continue adding remaining digits of longer list with carry until all nodes processed

B. Stop addition when shorter list ends and ignore remaining digits

C. Reverse both lists first then add digits

D. Convert lists to integers, add, then convert back to linked list

Solution

1. Step 1: Understand unequal length addition

   When one list ends, continue adding remaining digits of longer list plus carry.

2. Step 2: Maintain carry and process all nodes

   Carry from previous additions must be added until no nodes or carry remain.

3. Final Answer:

   Continue adding remaining digits of longer list with carry until all nodes processed -> Option A

4. Quick Check:

   Process all digits and carry regardless of list lengths [OK]

Hint: Add all digits and carry until both lists and carry are empty [OK]

Common Mistakes:

• Stopping addition early ignoring leftover digits
• Not adding carry after lists end
• Reversing lists unnecessarily