Merge two sorted lists in Rust
up vote
3
down vote
favorite
I wrote the following code to merge two sorted lists. Is there a way I can improve it?
Possible ideas (not sure how to implement them):
- Remove code duplication (setting the returning list node and moving to the next)
- Avoid the use of the infinite
loop
- Avoid the use of
panic!
This is the data structure:
type Link = Option<Box<Node>>;
pub struct Node {
elem: i32,
next: Link,
}
impl Node {
fn new(elem: i32) -> Node {
Node { elem, next: None }
}
}
And this is the method:
fn merge_sorted_lists(list1: &Link, list2: &Link) -> Link {
if list1.is_none() || list2.is_none() {
return None;
}
let mut res = None;
{
let mut node3 = &mut res;
let mut node1 = list1;
let mut node2 = list2;
loop {
if let (Some(link1), Some(link2)) = (node1, node2) {
if link1.elem > link2.elem {
*node3 = Some(Box::new(Node::new(link2.elem)));
node2 = &link2.next;
} else {
*node3 = Some(Box::new(Node::new(link1.elem)));
node1 = &link1.next;
}
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else if let Some(link1) = node1 {
*node3 = Some(Box::new(Node::new(link1.elem)));
node1 = &link1.next;
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else if let Some(link2) = node2 {
*node3 = Some(Box::new(Node::new(link2.elem)));
node1 = &link2.next;
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else {
break;
}
}
}
res
}
linked-list rust
bumped to the homepage by Community♦ 17 hours ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
up vote
3
down vote
favorite
I wrote the following code to merge two sorted lists. Is there a way I can improve it?
Possible ideas (not sure how to implement them):
- Remove code duplication (setting the returning list node and moving to the next)
- Avoid the use of the infinite
loop
- Avoid the use of
panic!
This is the data structure:
type Link = Option<Box<Node>>;
pub struct Node {
elem: i32,
next: Link,
}
impl Node {
fn new(elem: i32) -> Node {
Node { elem, next: None }
}
}
And this is the method:
fn merge_sorted_lists(list1: &Link, list2: &Link) -> Link {
if list1.is_none() || list2.is_none() {
return None;
}
let mut res = None;
{
let mut node3 = &mut res;
let mut node1 = list1;
let mut node2 = list2;
loop {
if let (Some(link1), Some(link2)) = (node1, node2) {
if link1.elem > link2.elem {
*node3 = Some(Box::new(Node::new(link2.elem)));
node2 = &link2.next;
} else {
*node3 = Some(Box::new(Node::new(link1.elem)));
node1 = &link1.next;
}
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else if let Some(link1) = node1 {
*node3 = Some(Box::new(Node::new(link1.elem)));
node1 = &link1.next;
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else if let Some(link2) = node2 {
*node3 = Some(Box::new(Node::new(link2.elem)));
node1 = &link2.next;
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else {
break;
}
}
}
res
}
linked-list rust
bumped to the homepage by Community♦ 17 hours ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I wrote the following code to merge two sorted lists. Is there a way I can improve it?
Possible ideas (not sure how to implement them):
- Remove code duplication (setting the returning list node and moving to the next)
- Avoid the use of the infinite
loop
- Avoid the use of
panic!
This is the data structure:
type Link = Option<Box<Node>>;
pub struct Node {
elem: i32,
next: Link,
}
impl Node {
fn new(elem: i32) -> Node {
Node { elem, next: None }
}
}
And this is the method:
fn merge_sorted_lists(list1: &Link, list2: &Link) -> Link {
if list1.is_none() || list2.is_none() {
return None;
}
let mut res = None;
{
let mut node3 = &mut res;
let mut node1 = list1;
let mut node2 = list2;
loop {
if let (Some(link1), Some(link2)) = (node1, node2) {
if link1.elem > link2.elem {
*node3 = Some(Box::new(Node::new(link2.elem)));
node2 = &link2.next;
} else {
*node3 = Some(Box::new(Node::new(link1.elem)));
node1 = &link1.next;
}
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else if let Some(link1) = node1 {
*node3 = Some(Box::new(Node::new(link1.elem)));
node1 = &link1.next;
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else if let Some(link2) = node2 {
*node3 = Some(Box::new(Node::new(link2.elem)));
node1 = &link2.next;
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else {
break;
}
}
}
res
}
linked-list rust
I wrote the following code to merge two sorted lists. Is there a way I can improve it?
Possible ideas (not sure how to implement them):
- Remove code duplication (setting the returning list node and moving to the next)
- Avoid the use of the infinite
loop
- Avoid the use of
panic!
This is the data structure:
type Link = Option<Box<Node>>;
pub struct Node {
elem: i32,
next: Link,
}
impl Node {
fn new(elem: i32) -> Node {
Node { elem, next: None }
}
}
And this is the method:
fn merge_sorted_lists(list1: &Link, list2: &Link) -> Link {
if list1.is_none() || list2.is_none() {
return None;
}
let mut res = None;
{
let mut node3 = &mut res;
let mut node1 = list1;
let mut node2 = list2;
loop {
if let (Some(link1), Some(link2)) = (node1, node2) {
if link1.elem > link2.elem {
*node3 = Some(Box::new(Node::new(link2.elem)));
node2 = &link2.next;
} else {
*node3 = Some(Box::new(Node::new(link1.elem)));
node1 = &link1.next;
}
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else if let Some(link1) = node1 {
*node3 = Some(Box::new(Node::new(link1.elem)));
node1 = &link1.next;
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else if let Some(link2) = node2 {
*node3 = Some(Box::new(Node::new(link2.elem)));
node1 = &link2.next;
if let Some(link) = {node3} {
node3 = &mut link.next;
} else {
panic!();
}
} else {
break;
}
}
}
res
}
linked-list rust
linked-list rust
edited Nov 11 at 12:11
asked Nov 11 at 11:41
Nick
14015
14015
bumped to the homepage by Community♦ 17 hours ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
bumped to the homepage by Community♦ 17 hours ago
This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
One problem in your current code is that you allocate the merged list, that could be what the user want but that not very flexible, a better way would be to consume the list, and let the user do a copy before if needed.
One other problem is that you have spaghetti code, it's very difficult to maintain and error prone.
you should also use generic to allow an user to have any type in your linked list.
To solve these problem you could use recursion, the typical use case match yours, so I would simply rework all your code to use it:
type Link<T> = Option<Box<Node<T>>>;
#[derive(Debug, Clone)]
pub struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> Node<T> {
// rework of new to make it more flexible
fn new(elem: T, next: Link<T>) -> Self {
Self { elem, next }
}
// next allow to change to linked node and to return the old one
fn next(&mut self, next: Link<T>) -> Link<T> {
std::mem::replace(&mut self.next, next)
}
fn elem(&self) -> &T {
&self.elem
}
// now we take by value and allow user to have a flexible control with f
fn merge_by<F>(a: Link<T>, b: Link<T>, accu: Link<T>, f: F) -> Link<T>
where
F: Fn(&T, &T) -> bool,
{
match (a, b) {
(Some(mut a), Some(mut b)) => {
if f(a.elem(), b.elem()) {
Self::merge_by(a.next(accu), Some(b), Some(a), f)
} else {
Self::merge_by(Some(a), b.next(accu), Some(b), f)
}
}
(Some(a), None) => Self::rev(accu, Some(a)),
(None, Some(b)) => Self::rev(accu, Some(b)),
(None, None) => Self::rev(accu, None),
}
}
// rev is needed when you deal with list
fn rev(list: Link<T>, accu: Link<T>) -> Link<T> {
match list {
Some(mut list) => Self::rev(list.next(accu), Some(list)),
None => accu,
}
}
}
fn main() {
let a = Some(Box::new(Node::new(21, Some(Box::new(Node::new(42, None))))));
println!("{:#?}", a);
let b = Some(Box::new(Node::new(1, Some(Box::new(Node::new(2, None))))));
println!("{:#?}", b);
let c = Node::merge_by(a, b, None, std::cmp::PartialEq::eq);
println!("{:#?}", c);
}
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
One problem in your current code is that you allocate the merged list, that could be what the user want but that not very flexible, a better way would be to consume the list, and let the user do a copy before if needed.
One other problem is that you have spaghetti code, it's very difficult to maintain and error prone.
you should also use generic to allow an user to have any type in your linked list.
To solve these problem you could use recursion, the typical use case match yours, so I would simply rework all your code to use it:
type Link<T> = Option<Box<Node<T>>>;
#[derive(Debug, Clone)]
pub struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> Node<T> {
// rework of new to make it more flexible
fn new(elem: T, next: Link<T>) -> Self {
Self { elem, next }
}
// next allow to change to linked node and to return the old one
fn next(&mut self, next: Link<T>) -> Link<T> {
std::mem::replace(&mut self.next, next)
}
fn elem(&self) -> &T {
&self.elem
}
// now we take by value and allow user to have a flexible control with f
fn merge_by<F>(a: Link<T>, b: Link<T>, accu: Link<T>, f: F) -> Link<T>
where
F: Fn(&T, &T) -> bool,
{
match (a, b) {
(Some(mut a), Some(mut b)) => {
if f(a.elem(), b.elem()) {
Self::merge_by(a.next(accu), Some(b), Some(a), f)
} else {
Self::merge_by(Some(a), b.next(accu), Some(b), f)
}
}
(Some(a), None) => Self::rev(accu, Some(a)),
(None, Some(b)) => Self::rev(accu, Some(b)),
(None, None) => Self::rev(accu, None),
}
}
// rev is needed when you deal with list
fn rev(list: Link<T>, accu: Link<T>) -> Link<T> {
match list {
Some(mut list) => Self::rev(list.next(accu), Some(list)),
None => accu,
}
}
}
fn main() {
let a = Some(Box::new(Node::new(21, Some(Box::new(Node::new(42, None))))));
println!("{:#?}", a);
let b = Some(Box::new(Node::new(1, Some(Box::new(Node::new(2, None))))));
println!("{:#?}", b);
let c = Node::merge_by(a, b, None, std::cmp::PartialEq::eq);
println!("{:#?}", c);
}
add a comment |
up vote
0
down vote
One problem in your current code is that you allocate the merged list, that could be what the user want but that not very flexible, a better way would be to consume the list, and let the user do a copy before if needed.
One other problem is that you have spaghetti code, it's very difficult to maintain and error prone.
you should also use generic to allow an user to have any type in your linked list.
To solve these problem you could use recursion, the typical use case match yours, so I would simply rework all your code to use it:
type Link<T> = Option<Box<Node<T>>>;
#[derive(Debug, Clone)]
pub struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> Node<T> {
// rework of new to make it more flexible
fn new(elem: T, next: Link<T>) -> Self {
Self { elem, next }
}
// next allow to change to linked node and to return the old one
fn next(&mut self, next: Link<T>) -> Link<T> {
std::mem::replace(&mut self.next, next)
}
fn elem(&self) -> &T {
&self.elem
}
// now we take by value and allow user to have a flexible control with f
fn merge_by<F>(a: Link<T>, b: Link<T>, accu: Link<T>, f: F) -> Link<T>
where
F: Fn(&T, &T) -> bool,
{
match (a, b) {
(Some(mut a), Some(mut b)) => {
if f(a.elem(), b.elem()) {
Self::merge_by(a.next(accu), Some(b), Some(a), f)
} else {
Self::merge_by(Some(a), b.next(accu), Some(b), f)
}
}
(Some(a), None) => Self::rev(accu, Some(a)),
(None, Some(b)) => Self::rev(accu, Some(b)),
(None, None) => Self::rev(accu, None),
}
}
// rev is needed when you deal with list
fn rev(list: Link<T>, accu: Link<T>) -> Link<T> {
match list {
Some(mut list) => Self::rev(list.next(accu), Some(list)),
None => accu,
}
}
}
fn main() {
let a = Some(Box::new(Node::new(21, Some(Box::new(Node::new(42, None))))));
println!("{:#?}", a);
let b = Some(Box::new(Node::new(1, Some(Box::new(Node::new(2, None))))));
println!("{:#?}", b);
let c = Node::merge_by(a, b, None, std::cmp::PartialEq::eq);
println!("{:#?}", c);
}
add a comment |
up vote
0
down vote
up vote
0
down vote
One problem in your current code is that you allocate the merged list, that could be what the user want but that not very flexible, a better way would be to consume the list, and let the user do a copy before if needed.
One other problem is that you have spaghetti code, it's very difficult to maintain and error prone.
you should also use generic to allow an user to have any type in your linked list.
To solve these problem you could use recursion, the typical use case match yours, so I would simply rework all your code to use it:
type Link<T> = Option<Box<Node<T>>>;
#[derive(Debug, Clone)]
pub struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> Node<T> {
// rework of new to make it more flexible
fn new(elem: T, next: Link<T>) -> Self {
Self { elem, next }
}
// next allow to change to linked node and to return the old one
fn next(&mut self, next: Link<T>) -> Link<T> {
std::mem::replace(&mut self.next, next)
}
fn elem(&self) -> &T {
&self.elem
}
// now we take by value and allow user to have a flexible control with f
fn merge_by<F>(a: Link<T>, b: Link<T>, accu: Link<T>, f: F) -> Link<T>
where
F: Fn(&T, &T) -> bool,
{
match (a, b) {
(Some(mut a), Some(mut b)) => {
if f(a.elem(), b.elem()) {
Self::merge_by(a.next(accu), Some(b), Some(a), f)
} else {
Self::merge_by(Some(a), b.next(accu), Some(b), f)
}
}
(Some(a), None) => Self::rev(accu, Some(a)),
(None, Some(b)) => Self::rev(accu, Some(b)),
(None, None) => Self::rev(accu, None),
}
}
// rev is needed when you deal with list
fn rev(list: Link<T>, accu: Link<T>) -> Link<T> {
match list {
Some(mut list) => Self::rev(list.next(accu), Some(list)),
None => accu,
}
}
}
fn main() {
let a = Some(Box::new(Node::new(21, Some(Box::new(Node::new(42, None))))));
println!("{:#?}", a);
let b = Some(Box::new(Node::new(1, Some(Box::new(Node::new(2, None))))));
println!("{:#?}", b);
let c = Node::merge_by(a, b, None, std::cmp::PartialEq::eq);
println!("{:#?}", c);
}
One problem in your current code is that you allocate the merged list, that could be what the user want but that not very flexible, a better way would be to consume the list, and let the user do a copy before if needed.
One other problem is that you have spaghetti code, it's very difficult to maintain and error prone.
you should also use generic to allow an user to have any type in your linked list.
To solve these problem you could use recursion, the typical use case match yours, so I would simply rework all your code to use it:
type Link<T> = Option<Box<Node<T>>>;
#[derive(Debug, Clone)]
pub struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> Node<T> {
// rework of new to make it more flexible
fn new(elem: T, next: Link<T>) -> Self {
Self { elem, next }
}
// next allow to change to linked node and to return the old one
fn next(&mut self, next: Link<T>) -> Link<T> {
std::mem::replace(&mut self.next, next)
}
fn elem(&self) -> &T {
&self.elem
}
// now we take by value and allow user to have a flexible control with f
fn merge_by<F>(a: Link<T>, b: Link<T>, accu: Link<T>, f: F) -> Link<T>
where
F: Fn(&T, &T) -> bool,
{
match (a, b) {
(Some(mut a), Some(mut b)) => {
if f(a.elem(), b.elem()) {
Self::merge_by(a.next(accu), Some(b), Some(a), f)
} else {
Self::merge_by(Some(a), b.next(accu), Some(b), f)
}
}
(Some(a), None) => Self::rev(accu, Some(a)),
(None, Some(b)) => Self::rev(accu, Some(b)),
(None, None) => Self::rev(accu, None),
}
}
// rev is needed when you deal with list
fn rev(list: Link<T>, accu: Link<T>) -> Link<T> {
match list {
Some(mut list) => Self::rev(list.next(accu), Some(list)),
None => accu,
}
}
}
fn main() {
let a = Some(Box::new(Node::new(21, Some(Box::new(Node::new(42, None))))));
println!("{:#?}", a);
let b = Some(Box::new(Node::new(1, Some(Box::new(Node::new(2, None))))));
println!("{:#?}", b);
let c = Node::merge_by(a, b, None, std::cmp::PartialEq::eq);
println!("{:#?}", c);
}
edited Nov 11 at 15:22
answered Nov 11 at 14:21
Stargateur
21815
21815
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207418%2fmerge-two-sorted-lists-in-rust%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown