Add Two Numbers Represented as Linked List in DSA Rust - Build from Scratch

Add Two Numbers Represented as Linked List

📖 Scenario: Imagine you have two numbers, but each digit is stored in a linked list node. Each node holds one digit, and the digits are stored in reverse order. For example, the number 342 is stored as 2 -> 4 -> 3 -> null. You want to add these two numbers and get the result as a linked list in the same reversed format.

🎯 Goal: You will build a Rust program that creates two linked lists representing numbers, adds them digit by digit, and prints the resulting linked list showing the sum.

📋 What You'll Learn

Create two linked lists representing the numbers 342 and 465 respectively.

Create a helper variable to track the carry during addition.

Write the core logic to add the two numbers digit by digit using linked list traversal.

Print the resulting linked list showing the sum in reversed order.

💡 Why This Matters

🌍 Real World

Adding numbers digit by digit is similar to how calculators or computers handle large numbers that don't fit in normal variables. Linked lists help store such numbers efficiently.

💼 Career

Understanding linked lists and how to manipulate them is important for software engineers working with low-level data structures, memory management, or implementing custom arithmetic operations.

1

Create two linked lists representing the numbers

Create two linked lists called l1 and l2 representing the numbers 342 and 465 respectively. Each node should hold one digit, and the digits should be stored in reverse order. Use the ListNode struct provided.

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

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

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

fn main() {
    // Create linked list l1 representing 342
    // Create linked list l2 representing 465
    // Your code here
}

Hint

Start by creating the first node for each list using ListNode::new(). Then link the next nodes by setting the next field.

2

Create a carry variable for addition

Create a variable called carry and set it to 0. This will help keep track of the carry when adding digits.

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

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

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

fn main() {
    // Create linked list l1 representing 342: 2 -> 4 -> 3
    let l1 = ListNode::new(2);
    l1.borrow_mut().next = Some(ListNode::new(4));
    l1.borrow().next.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(3));

    // Create linked list l2 representing 465: 5 -> 6 -> 4
    let l2 = ListNode::new(5);
    l2.borrow_mut().next = Some(ListNode::new(6));
    l2.borrow().next.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(4));

    // Create a carry variable
    // Your code here
}

Hint

Use let mut carry = 0; to create a variable that can change during addition.

3

Add the two numbers digit by digit

Write the core logic to add the two numbers digit by digit. Use variables p and q to traverse l1 and l2 respectively. Create a new linked list dummy_head to store the result. Use a variable current to build the result list. Add digits and carry, update carry, and move pointers until both lists are fully traversed and carry is zero.

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

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

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

fn main() {
    // Create linked list l1 representing 342: 2 -> 4 -> 3
    let l1 = ListNode::new(2);
    l1.borrow_mut().next = Some(ListNode::new(4));
    l1.borrow().next.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(3));

    // Create linked list l2 representing 465: 5 -> 6 -> 4
    let l2 = ListNode::new(5);
    l2.borrow_mut().next = Some(ListNode::new(6));
    l2.borrow().next.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(4));

    // Create a carry variable
    let mut carry = 0;

    // Add the two numbers digit by digit
    // Your code here
}

Hint

Use a while loop to continue as long as p or q has nodes or carry is not zero. Extract values from nodes or use 0 if none. Calculate sum and carry. Create new nodes for the result list.

4

Print the resulting linked list

Print the resulting linked list starting from dummy_head.next. Traverse the list and print each node's value followed by ->. End with null to show the list ends.

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

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

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

fn main() {
    // Create linked list l1 representing 342: 2 -> 4 -> 3
    let l1 = ListNode::new(2);
    l1.borrow_mut().next = Some(ListNode::new(4));
    l1.borrow().next.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(3));

    // Create linked list l2 representing 465: 5 -> 6 -> 4
    let l2 = ListNode::new(5);
    l2.borrow_mut().next = Some(ListNode::new(6));
    l2.borrow().next.as_ref().unwrap().borrow_mut().next = Some(ListNode::new(4));

    // Create a carry variable
    let mut carry = 0;

    let mut p = Some(l1.clone());
    let mut q = Some(l2.clone());
    let dummy_head = ListNode::new(0);
    let mut current = dummy_head.clone();

    while p.is_some() || q.is_some() || carry != 0 {
        let x = if let Some(node) = &p {
            node.borrow().val
        } else {
            0
        };
        let y = if let Some(node) = &q {
            node.borrow().val
        } else {
            0
        };

        let sum = carry + x + y;
        carry = sum / 10;
        let new_node = ListNode::new(sum % 10);
        current.borrow_mut().next = Some(new_node.clone());
        current = new_node;

        p = if let Some(node) = p {
            node.borrow().next.clone()
        } else {
            None
        };
        q = if let Some(node) = q {
            node.borrow().next.clone()
        } else {
            None
        };
    }

    // Print the resulting linked list
    // Your code here
}

Hint

Start from dummy_head.next and loop through each node. Print the value followed by ->. After the loop, print null to show the end.

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