Add Two Numbers Represented as Linked List in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after adding two linked lists?

Given two linked lists representing numbers in reverse order, what is the resulting linked list after adding them?

DSA Rust

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

fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut p = l1;
    let mut q = l2;
    let mut carry = 0;
    let mut dummy = Box::new(ListNode { val: 0, next: None });
    let mut current = &mut dummy;

    while p.is_some() || q.is_some() || carry != 0 {
        let sum = carry + p.as_ref().map_or(0, |node| node.val) + q.as_ref().map_or(0, |node| node.val);
        carry = sum / 10;
        current.next = Some(Box::new(ListNode { val: sum % 10, next: None }));
        current = current.next.as_mut().unwrap();
        p = p.and_then(|node| node.next);
        q = q.and_then(|node| node.next);
    }

    dummy.next
}

// Input lists:
// l1: 2 -> 4 -> 3 -> null (represents 342)
// l2: 5 -> 6 -> 4 -> null (represents 465)
// What is the output linked list?

A 8 -> 0 -> 7 -> null

B 7 -> 0 -> 7 -> null

C 7 -> 0 -> 8 -> null

D 7 -> 1 -> 7 -> null

💡 Hint

Add digits node by node, carry over if sum >= 10.

Adding 342 + 465 = 807. The linked list stores digits in reverse order: 7 -> 0 -> 8 -> null.

🧠 Conceptual

intermediate

Why do we use a dummy head node in linked list addition?

In the function to add two numbers represented by linked lists, why is a dummy head node used?

A To simplify handling the head of the result list and avoid special cases.

B To store the carry value during addition.

C To reverse the input linked lists before addition.

D To keep track of the length of the linked lists.

💡 Hint

Think about how to easily add nodes to the result list.

A dummy head node allows us to easily append nodes without checking if the list is empty, avoiding special cases for the first node.

🔧 Debug

advanced

What error occurs in this Rust code for adding two numbers as linked lists?

Identify the error when running this Rust function to add two numbers represented as linked lists: fn add_two_numbers(l1: Option>, l2: Option>) -> Option> { let mut p = l1; let mut q = l2; let mut carry = 0; let mut dummy = Box::new(ListNode { val: 0, next: None }); let mut current = &mut dummy; while p.is_some() || q.is_some() || carry != 0 { let sum = carry + p.unwrap().val + q.unwrap().val; carry = sum / 10; current.next = Some(Box::new(ListNode { val: sum % 10, next: None })); current = current.next.as_mut().unwrap(); p = p.unwrap().next; q = q.unwrap().next; } dummy.next }

A panic at unwrap on None value

B SyntaxError due to missing semicolon

C TypeError due to mismatched types

D Infinite loop without termination

💡 Hint

Check how unwrap() is used on Option values inside the loop.

Calling unwrap() on None causes a panic. The code does not check if p or q is Some before unwrap, leading to runtime error.

🚀 Application

advanced

How to handle different length linked lists in addition?

When adding two numbers represented by linked lists of different lengths, how should the code handle the shorter list?

A Stop addition when the shorter list ends.

B Treat missing nodes as 0 during addition.

C Pad the shorter list with nodes of value 1.

D Reverse both lists before adding.

💡 Hint

Think about what value to add when one list has no node.

Missing nodes are treated as 0 so addition continues correctly until both lists and carry are processed.

❓ Predict Output

expert

What is the output linked list after adding these two numbers?

Given the following input linked lists representing numbers in reverse order, what is the output linked list after addition? l1: 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> null (represents 9,999,999) l2: 9 -> 9 -> 9 -> 9 -> null (represents 9,999) Use the standard addition method with carry.

DSA Rust

// Function and ListNode struct as usual
// Input lists:
// l1: 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> null
// l2: 9 -> 9 -> 9 -> 9 -> null
// What is the output linked list?

A 8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 0 -> null

B 8 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 1 -> null

C 0 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1 -> null

D 8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1 -> null

💡 Hint

Add digit by digit with carry, note the extra node for carry at the end.

Adding 9,999,999 + 9,999 = 10,009,998. The linked list in reverse is 8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1 -> null.

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