Merge Two Sorted Linked Lists in DSA Rust - Build from Scratch

Merge Two Sorted Linked Lists

📖 Scenario: You are working on a simple contact list app. The contacts are stored in two separate sorted linked lists by their names. You want to merge these two lists into one sorted linked list so that the app can display all contacts in order.

🎯 Goal: Build a Rust program that merges two sorted linked lists of strings into one sorted linked list and prints the merged list.

📋 What You'll Learn

Create two sorted linked lists of strings named list1 and list2

Create a helper variable dummy as the start of the merged list

Write a function merge_lists that merges list1 and list2 into one sorted linked list

Print the merged linked list in the format: "Alice -> Bob -> Charlie -> null"

💡 Why This Matters

🌍 Real World

Merging sorted linked lists is useful in contact management apps, event scheduling, and anywhere sorted data from multiple sources needs to be combined.

💼 Career

Understanding linked list operations and merging algorithms is important for software engineering roles that involve data structure manipulation and optimization.

1

Create two sorted linked lists

Create two sorted linked lists named list1 and list2 using the ListNode struct. list1 should contain "Alice" and "Charlie". list2 should contain "Bob" and "David".

DSA Rust

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

#[derive(Debug, Clone)]
struct ListNode {
    val: String,
    next: Option>>,
}

impl ListNode {
    fn new(val: String) -> Rc> {
        Rc::new(RefCell::new(ListNode { val, next: None }))
    }
}

fn main() {
    // Create list1 with "Alice" -> "Charlie"
    // Create list2 with "Bob" -> "David"
    // Your code here
}

Hint

Use ListNode::new to create nodes. Link nodes by setting next with Some(node). Wrap the first node in Some to create the list.

2

Create a dummy node for merging

Create a variable called dummy as a new ListNode with an empty string "". Also create a mutable variable tail and set it equal to dummy.clone().

DSA Rust

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

#[derive(Debug, Clone)]
struct ListNode {
    val: String,
    next: Option>>,
}

impl ListNode {
    fn new(val: String) -> Rc> {
        Rc::new(RefCell::new(ListNode { val, next: None }))
    }
}

fn main() {
    let node1 = ListNode::new("Alice".to_string());
    let node2 = ListNode::new("Charlie".to_string());
    node1.borrow_mut().next = Some(node2.clone());
    let list1 = Some(node1.clone());

    let node3 = ListNode::new("Bob".to_string());
    let node4 = ListNode::new("David".to_string());
    node3.borrow_mut().next = Some(node4.clone());
    let list2 = Some(node3.clone());

    // Create dummy node and tail pointer
    // Your code here
}

Hint

Create a dummy node with an empty string. Use clone() to make tail point to the dummy.

3

Write the merge function

Write a function called merge_lists that takes two parameters list1 and list2 of type Option<Rc<RefCell<ListNode>>>. Inside main, call merge_lists(list1.clone(), list2.clone()) and assign the result to merged. The function should merge the two sorted lists into one sorted linked list by comparing the val strings lexicographically and return the merged list starting after the dummy node.

DSA Rust

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

#[derive(Debug, Clone)]
struct ListNode {
    val: String,
    next: Option>>,
}

impl ListNode {
    fn new(val: String) -> Rc> {
        Rc::new(RefCell::new(ListNode { val, next: None }))
    }
}

fn main() {
    let node1 = ListNode::new("Alice".to_string());
    let node2 = ListNode::new("Charlie".to_string());
    node1.borrow_mut().next = Some(node2.clone());
    let list1 = Some(node1.clone());

    let node3 = ListNode::new("Bob".to_string());
    let node4 = ListNode::new("David".to_string());
    node3.borrow_mut().next = Some(node4.clone());
    let list2 = Some(node3.clone());

    let dummy = ListNode::new("".to_string());
    let mut tail = dummy.clone();

    // Call merge_lists and assign to merged
    // Your code here
}

// Write the merge_lists function below
// Your code here

Hint

Use a dummy node and a tail pointer. Compare val strings of current nodes in list1 and list2. Append the smaller one to tail.next and move pointers forward. Return dummy.next at the end.

4

Print the merged linked list

Write a function called print_list that takes an Option<Rc<RefCell<ListNode>>> and prints the linked list values separated by " -> " and ending with "null". Call print_list(merged) inside main to display the merged list.

DSA Rust

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

#[derive(Debug, Clone)]
struct ListNode {
    val: String,
    next: Option>>,
}

impl ListNode {
    fn new(val: String) -> Rc> {
        Rc::new(RefCell::new(ListNode { val, next: None }))
    }
}

fn merge_lists(
    mut list1: Option>>,
    mut list2: Option>>,
) -> Option>> {
    let dummy = ListNode::new("".to_string());
    let mut tail = dummy.clone();

    while list1.is_some() && list2.is_some() {
        let val1 = list1.as_ref().unwrap().borrow().val.clone();
        let val2 = list2.as_ref().unwrap().borrow().val.clone();

        if val1 <= val2 {
            let next = list1.as_ref().unwrap().borrow_mut().next.take();
            tail.borrow_mut().next = list1.clone();
            tail = tail.borrow().next.as_ref().unwrap().clone();
            list1 = next;
        } else {
            let next = list2.as_ref().unwrap().borrow_mut().next.take();
            tail.borrow_mut().next = list2.clone();
            tail = tail.borrow().next.as_ref().unwrap().clone();
            list2 = next;
        }
    }

    if list1.is_some() {
        tail.borrow_mut().next = list1;
    } else {
        tail.borrow_mut().next = list2;
    }

    dummy.borrow().next.clone()
}

fn main() {
    let node1 = ListNode::new("Alice".to_string());
    let node2 = ListNode::new("Charlie".to_string());
    node1.borrow_mut().next = Some(node2.clone());
    let list1 = Some(node1.clone());

    let node3 = ListNode::new("Bob".to_string());
    let node4 = ListNode::new("David".to_string());
    node3.borrow_mut().next = Some(node4.clone());
    let list2 = Some(node3.clone());

    let dummy = ListNode::new("".to_string());
    let mut tail = dummy.clone();

    let merged = merge_lists(list1.clone(), list2.clone());

    // Call print_list to display merged list
    // Your code here
}

// Write print_list function here
// Your code here

Hint

Traverse the merged list from the head. Print each node's val followed by " -> ". After the last node, print "null" and a newline.

Practice

1. What is the main goal when merging two sorted linked lists?

easy

A. Reverse both linked lists

B. Remove duplicates from both lists

C. Create a new sorted linked list containing all elements from both lists

D. Sort each list separately without merging

Solution

1. Step 1: Understand the problem

   Merging two sorted linked lists means combining them into one list that remains sorted.

2. Step 2: Identify the goal

   The goal is to create a new sorted linked list that contains all elements from both input lists.

3. Final Answer:

   Create a new sorted linked list containing all elements from both lists -> Option C

4. Quick Check:

   Merging = Combined sorted list [OK]

Hint: Merging means combining sorted lists into one sorted list [OK]

Common Mistakes:

• Thinking merging means reversing lists
• Trying to sort lists separately without merging
• Confusing merging with removing duplicates

2. Which Rust code snippet correctly declares a singly linked list node struct for merging?

easy

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

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

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

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

Solution

1. Step 1: Understand Rust linked list node

   Rust needs heap allocation for recursive types, so next must be Option.

2. Step 2: Check each option

   struct ListNode { val: i32, next: Option } uses Option, which is correct. Others use references or direct types causing errors.

3. Final Answer:

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

4. Quick Check:

   Use Option for linked list nodes [OK]

Hint: Use Option for recursive linked list nodes in Rust [OK]

Common Mistakes:

• Using direct ListNode type for next causes infinite size error
• Using references without lifetimes causes borrow errors
• Using Option<ListNode> misses boxing needed for recursion

3. Given two sorted linked lists where one list is empty and the other is 0 -> 2 -> 4 -> null, what is the merged list? How does the merge function handle this edge case?

let l1: Option = None;
let l2 = Some(Box::new(ListNode { val: 0, next: Some(Box::new(ListNode { val: 2, next: Some(Box::new(ListNode { val: 4, next: None })) })) }));

let merged = merge_two_lists(l1, l2);

easy

A. 0 -> 2 -> 4 -> null

B. null

C. 0 -> null

D. 2 -> 4 -> null

Solution

1. Step 1: Check input lists

   l1 is None (empty), l2 is 0 -> 2 -> 4 -> null.

2. Step 2: Merge function returns non-empty list

   When one list is None, function returns the other list as is.

3. Final Answer:

   0 -> 2 -> 4 -> null -> Option A

4. Quick Check:

   Empty + list = list unchanged [OK]

Hint: If one list empty, merged list is the other list [OK]

Common Mistakes:

• Returning null when one list is empty
• Trying to merge empty list nodes incorrectly
• Losing nodes from non-empty list

4. What is the output linked list after merging these two sorted lists? List1: 1 -> 3 -> 5 -> null List2: 2 -> 4 -> 6 -> null

fn merge_two_lists(l1: Option, l2: Option) -> Option {
    match (l1, l2) {
        (None, None) => None,
        (Some(node), None) | (None, Some(node)) => Some(node),
        (Some(mut n1), Some(mut n2)) => {
            if n1.val < n2.val {
                n1.next = merge_two_lists(n1.next.take(), Some(n2));
                Some(n1)
            } else {
                n2.next = merge_two_lists(Some(n1), n2.next.take());
                Some(n2)
            }
        }
    }
}

medium

A. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

B. 1 -> 3 -> 5 -> 2 -> 4 -> 6 -> null

C. 2 -> 4 -> 6 -> 1 -> 3 -> 5 -> null

D. 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

Solution

1. Step 1: Trace first comparison

   Compare 1 and 2: 1 < 2, so 1 is first node.

2. Step 2: Recursively merge remaining lists

   Next merge 3->5 and 2->4->6. 2 < 3, so 2 next, then 3, 4, 5, 6.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null -> Option A

4. Quick Check:

   Sorted merge = 1,2,3,4,5,6 [OK]

Hint: Pick smaller head each step to merge sorted lists [OK]

Common Mistakes:

• Appending lists instead of merging sorted
• Not updating next pointers correctly
• Mixing order of nodes in merged list

5. Identify the bug in this Rust merge function and select the fix:

fn merge_two_lists(l1: Option, l2: Option) -> Option {
    match (l1, l2) {
        (None, None) => None,
        (Some(node), None) => Some(node),
        (None, Some(node)) => Some(node),
        (Some(mut n1), Some(mut n2)) => {
            if n1.val <= n2.val {
                n1.next = merge_two_lists(n1.next, Some(n2));
                Some(n1)
            } else {
                n2.next = merge_two_lists(Some(n1), n2.next);
                Some(n2)
            }
        }
    }
}

medium

A. Remove match and use if-else only

B. Change if condition to n1.val < n2.val

C. Replace Some(mut n1) with &mut n1

D. Use n1.next.take() and n2.next.take() to avoid borrowing errors

Solution

1. Step 1: Identify ownership issue

   n1.next and n2.next are Options; assigning without take() causes borrowing errors.

2. Step 2: Fix by using take()

   Using n1.next.take() and n2.next.take() moves ownership out safely for recursion.

3. Final Answer:

   Use n1.next.take() and n2.next.take() to avoid borrowing errors -> Option D

4. Quick Check:

   Use take() to move Option ownership [OK]

Hint: Use .take() to move Option values safely in Rust [OK]

Common Mistakes:

• Not using take() causes borrow checker errors
• Changing comparison operator unnecessarily
• Using references incorrectly in pattern matching