Add Two Numbers Represented as Linked List in DSA Rust

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 together, 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 boxes and carry over if the sum is more than 9, moving leftwards.

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

Dry Run Walkthrough

Input: list1: 2->4->3 (represents 342), list2: 5->6->4 (represents 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 to get final digit

Result:

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

Annotated Code

DSA Rust

use std::option::Option;
use std::boxed::Box;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

fn add_two_numbers(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut p1 = l1;
    let mut p2 = l2;
    let mut carry = 0;
    let mut dummy_head = Box::new(ListNode::new(0));
    let mut current = &mut dummy_head;

    while p1.is_some() || p2.is_some() || carry != 0 {
        let val1 = p1.as_ref().map_or(0, |node| node.val);
        let val2 = p2.as_ref().map_or(0, |node| node.val);
        let sum = val1 + val2 + carry;
        carry = sum / 10;
        let digit = sum % 10;

        current.next = Some(Box::new(ListNode::new(digit)));
        current = current.next.as_mut().unwrap();

        if let Some(node) = p1 {
            p1 = node.next;
        } else {
            p1 = None;
        }

        if let Some(node) = p2 {
            p2 = node.next;
        } else {
            p2 = None;
        }
    }

    dummy_head.next
}

fn build_list(nums: &[i32]) -> Option<Box<ListNode>> {
    let mut head = None;
    for &num in nums.iter().rev() {
        let mut node = Box::new(ListNode::new(num));
        node.next = head;
        head = Some(node);
    }
    head
}

fn print_list(list: &Option<Box<ListNode>>) {
    let mut current = list.as_ref();
    while let Some(node) = current {
        print!("{}", node.val);
        if node.next.is_some() {
            print!(" -> ");
        }
        current = node.next.as_ref();
    }
    println!(" -> null");
}

fn main() {
    let l1 = build_list(&[2, 4, 3]);
    let l2 = build_list(&[5, 6, 4]);
    let result = add_two_numbers(l1, l2);
    print_list(&result);
}

while p1.is_some() || p2.is_some() || carry != 0 {

continue adding while there are digits or carry

let val1 = p1.as_ref().map_or(0, |node| node.val);

get current digit from first list or 0 if none

let val2 = p2.as_ref().map_or(0, |node| node.val);

get current digit from second list or 0 if none

let sum = val1 + val2 + carry;

sum digits plus carry

carry = sum / 10;

calculate carry for next digit

let digit = sum % 10;

digit to store in current node

current.next = Some(Box::new(ListNode::new(digit)));

append new node with digit to result list

current = current.next.as_mut().unwrap();

move current pointer to new node

if let Some(node) = p1 { p1 = node.next; } else { p1 = None; }

advance pointer in first list

if let Some(node) = p2 { p2 = node.next; } else { p2 = None; }

advance pointer in second list

Output

7 -> 0 -> 8 -> null

Complexity Analysis

Time: O(n) because we traverse both linked lists once where n is the length of the longer list

Space: O(n) because the result list stores the sum digits, which can be at most one node longer than the longer input

vs Alternative: Compared to converting lists to numbers and back (which can overflow and is inefficient), this method works digit by digit and handles large numbers safely

Edge Cases

One list is empty

The function returns the other list as the sum

DSA Rust

while p1.is_some() || p2.is_some() || carry != 0 {

Sum produces an extra carry digit (e.g., 5 + 5 = 10)

An extra node is added to the result list to hold the carry

DSA Rust

while p1.is_some() || p2.is_some() || carry != 0 {

Lists of different lengths

Shorter list digits are treated as 0 after they end

DSA Rust

let val1 = p1.as_ref().map_or(0, |node| node.val);

When to Use This Pattern

When you see two linked lists representing numbers and need to add them digit by digit, use this pattern to simulate addition with carry, avoiding number conversion issues.

Common Mistakes

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

Mistake: Advancing pointers incorrectly causing infinite loops or skipping nodes
Fix: Advance pointers only if the current node exists, else set to None

Summary

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

Use when adding large numbers stored in linked lists without converting to integers.

The key is to add digits and carry stepwise, creating new nodes for the sum.

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