Hi, all
I'm following in the same footsteps of this thread and got stuck with the same problem. Is there some recommended reading to help people understand this subject in more detail? Are there any programming problems that one could do before tackling this one?
My problem is that I can't get to keep references to the head and to the tail of the list that I'm supposed to construct and return.
Hi and welcome, it’s generally good practice to open new topics instead of reviving super old ones (which ought to be closed automatically anyways, unless they’re so old that the auto-closing wasn’t enabled at the time), so I’ve moved your question here 
That said, I found (somebody's) recursive solution that doesn't require keeping two pointers to the same list. Quite possibly using a different approach to such problems is the way to go.
The solution you linked doesn't actually splice together the nodes of the two lists, rather, it creates new nodes and throws the nodes from the input list away. Here's another solution:
pub fn merge_two_lists(
l1: Option<Box<ListNode>>,
l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
let mut output = None;
let mut next_node_pos = &mut output;
let mut l1_opt = l1;
let mut l2_opt = l2;
loop {
let mut l1 = match l1_opt {
Some(l1) => l1,
None => { *next_node_pos = l2_opt; break; },
};
let mut l2 = match l2_opt {
Some(l2) => l2,
None => { *next_node_pos = Some(l1); break; },
};
if l1.val < l2.val {
l1_opt = l1.next.take();
l2_opt = Some(l2);
*next_node_pos = Some(l1);
} else {
l2_opt = l2.next.take();
l1_opt = Some(l1);
*next_node_pos = Some(l2);
}
next_node_pos = &mut next_node_pos.as_mut().unwrap().next;
}
output
}
Here’s a fun approach for solving this challenge: (as also suggested in the other thread), in Rust you’d typically work with iterators rather than linked lists. But these linked lists can be converted from and into iterators (of single-element nodes) like this:
type List = Option<Box<ListNode>>;
// Turns linked lists into an iterator of single-element list nodes
fn nodes(mut list: List) -> impl Iterator<Item = Box<ListNode>> {
std::iter::from_fn(move || {
let mut node = list.take()?;
list = node.next.take();
Some(node)
})
}
// (Re-)assembles linked list from iterator of single-element list nodes.
fn list_from_nodes(nodes: impl Iterator<Item = Box<ListNode>>) -> List {
let mut list = None;
let mut last = &mut list;
for node in nodes {
assert!(node.next.is_none(), "encountered non-single-element node!");
*last = Some(node);
last = &mut last.as_mut().unwrap().next;
}
list
}
Now the remaining task is to merge two of these kinds of iterators correctly,
fn merge_two_iterators(
left: impl Iterator<Item = Box<ListNode>>,
right: impl Iterator<Item = Box<ListNode>>,
) -> impl Iterator<Item = Box<ListNode>> {
// Both iterators made peekable so you can peek at the first items
// using left.peek() or right.peek(), without consuming the item yet.
// If you want to commit to consuming either, just call left.next(), or
// right.next(), respectively, and return the result
let mut left = left.peekable();
let mut right = right.peekable();
std::iter::from_fn(move || {
// this code is called repeatedly to create the next item.
todo!() // implement your solution here!
// return `None` from this closure once the iterator is complete,
// otherwise return `Some(…next item…)` to produce the next item.
// Try to just work with the `left` and `right` iterators from above
// as mutable state. Only consume one of their items with `….next()`
// once you *actually* want to return it here as the very next item
// to be produced.
})
}
(insert appropriate code in place of where it says todo!() above; feel free to give this a go! You can ask for help, if you need more information!!)
then you can assemble the solution as follows:
impl Solution {
pub fn merge_two_lists(list1: List, list2: List) -> List {
list_from_nodes(merge_two_iterators(nodes(list1), nodes(list2)))
}
}
Who knows, maybe this approach of converting into an iterator, and in the end back into a list, works good for some other challenges involving linked lists, too; perhaps for other challenges, some of the methods that Iterator provides could come in handy, too.
The classic ML solution to this is to only use lists as stacks, not queues. So you merge it in reverse order -- which is easy, since you're only ever looking at one end of a list -- then reverse it -- which is also easy since popping off one stack and pushing onto another reverses it.
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.