Jump to content
  • Advertisement
Sign in to follow this  
S_S

Merge Two Linked List

This topic is 5057 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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. ///

Share this post


Link to post
Share on other sites
Advertisement
Node* a = l1.begin();
Node* b = l2.begin();


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



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

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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 ;)

Share this post


Link to post
Share on other sites
More information is needed before a really good answer can be given. Are the two lists already sorted? If so, go with yaroslavd's answer. Otherwise, just add the lists together then go ahead and sort that list.

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

Share this post


Link to post
Share on other sites
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:
Original post by nmi
Check out this page.

Whilst the link nmi posted is okay, bear in mind that their documented extension to bitonic sort for arbitrary n that they use does not actually work in many cases, should you consider that algorithm. Their workaround for 'n not a power of two' is flawed and I can reproduce the same flaw in their applet also, producing an incorrect sort result. I tried contacting the author about this but got no response. The same workaround does actually work in breadth-first mergesort though.

yaroslavd has got the right idea, but you also need to be careful which way the lists are sorted - Increasing or decreasing order.

I assume that these are not doubly-linked lists that they are talking about?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!