• Create Account

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

8 replies to this topic

#1S_S  Members

122
Like
0Likes
Like

Posted 13 December 2004 - 10:44 AM

Sorry i am opening this topic but i have problem with this exercise. It is not homework but it is a sample question for midterm. I couldn't solve it. If you believe me (because i konw your behaviours for people who want homework assignments) , please help. Tomorrow i have a midterm :( /// Write a function to merge two linked lists of integers that are sorted into ascending order. The result should be a third linked list that is the sorted combination of the original lists. Do not destroy the original lists. ///

#2yaroslavd  Members

150
Like
0Likes
Like

Posted 13 December 2004 - 10:53 AM

Node* a = l1.begin();
Node* b = l2.begin();

while (...)
{
if(*a<*b)
{
a = a->next();
}
else
{
b = b->next();
}
}

And then take care of if either a or b reaches the end of its list.

#3S_S  Members

122
Like
0Likes
Like

Posted 13 December 2004 - 10:57 AM

but how can i write it in c++ ?

#4Enigma  Members

1402
Like
0Likes
Like

Posted 13 December 2004 - 11:00 AM

std::list merged = std::list(list1).merge(std::list(list2));

std::list<int> merged(list1);
std::list<int> merged2(list2);
merged.merge(merged2);

Enigma

EDIT: Oops, should have checked that what I posted would actually compile!

[Edited by - Enigma on December 13, 2004 5:00:04 PM]

#5yaroslavd  Members

150
Like
0Likes
Like

Posted 13 December 2004 - 11:00 AM

That IS in C++. I mean it's pseudocode but it's basically C++. The only thing that's left for you to fill in is the condition on the while loop and some checks.

#6JuNC  Members

236
Like
0Likes
Like

Posted 13 December 2004 - 11:01 AM

l1 is list 1
l2 is list 2

let append_and_sort l1 l2 =
let l = List.append l1 l2 in
List.sort (compare) l

Hints:

a) Specify programming language if you want specific answers (don't expect this for homework though).
b) Show your working, although you say this isn't homework, you've given no real evidence to the contrary. Without giving us what *you've* done working towards the problem the rules say we musn't help you.

EDIT: this was written before the three replies ;)

#7choffstein  Members

1090
Like
0Likes
Like

Posted 13 December 2004 - 11:19 AM

I have no experience in sorting linked lists, but I would probably just put all the addresses in an array of int *, (removing each node from the list), perform a merge sort on the _values_ at the addresses, then recreate the list. Probably the simplest method. If you are pressed for time, I am sure a simple insertion sort could be done. No need to over complicate things.

Good luck!
-visage

#8nmi  Members

978
Like
0Likes
Like

Posted 13 December 2004 - 11:28 AM

#9iMalc  Members

2466
Like
0Likes
Like

Posted 13 December 2004 - 06:18 PM

An implementation of Merge Sort should not involve any array of pointers. Doing so would make it far more complicated and inferrior performance-wise. You merely divide the list into two and recurse on each half unless a list only has 1 item. Then after the recursive calls you merge the lists together.

Quote: