Merge Two Linked List
Members - Reputation: 122
Posted 13 December 2004 - 10:44 AM
Members - Reputation: 1402
Posted 13 December 2004 - 11:00 AM
EDIT: Oops, should have checked that what I posted would actually compile!
[Edited by - Enigma on December 13, 2004 5:00:04 PM]
Members - Reputation: 236
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
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 ;)
Members - Reputation: 1090
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.
Crossbones+ - Reputation: 2450
Posted 13 December 2004 - 06:18 PM
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?