HI again,
Thanks for respond,
Here is the code:
SNIP YOUR CODE.
I would agree with Mr Harrison that if you can use the sort template then
do so. However if you have to implement a sort of a linked list yourself,
then using quicksort is not one of the better methods to use because of
its O(N^2) behavior when the list is already sorted or inverse sorted. Also
quicksort will have a stack size of O(N) if the input is near sorted or
inverse sorted. A much better method would be to use a merge sort. A merge
sort will always have O(N log N) behavior and the stack depth will be
O(log N) which will eliminate your problem with the stack blowing up.
A quick pseudo code for a merge sort follows:
LIST * sort(LIST * input)
{
LIST * list1;
LIST * list2;
LIST * tail;
LIST * head;
// If input list is empty or has only 1 node, return it */
if (input == NULL || input->next == NULL) return input;
// Only lists of length 2 or greater will reach this point.
// Split input list into 2 approximately equal sized lists.
// Method used here is to have 2 pointers, a fast pointer and a slow
// pointer where the fast pointer moves twice as fast as the slow
// pointer. When the fast pointer reaches the end of the list, the
// slow pointer will be pointing to the last node of one of the desired
// half lists.
list1 = input;
list2 = input;
tail = input;
for(;
{
tail = tail->next;
if (tail == NULL) break;
tail = tail->next;
if (tail == NULL) break;
list2 = list2->next;
}
tail = list2; // Split input list into 2 smaller lists
list2 = tail->next;
tail->next = NULL;
// Now recursively sort the 2 smaller lists.
list1 = sort(list1);
list2 = sort(list2);
// Now merge the 2 lists together
// Note: Both list1 and list2 will be non-empty because of
// the IF statement at the beginning of the function.
if (compare(*list1, *list2) < 0) {
head = list1;
tail = list1;
list1 = list1->next;
} else {
head = list2;
tail = list2;
list2 = list2->next;
}
// Continue to merge nodes as long as both lists are not empty.
while(list1 != NULL && list2 != NULL) {
if (compare(*list1, *list2) < 0) {
tail->next = list1;
tail = list1;
list1 = list1->next;
} else {
tail->next = list2;
tail = list2;
list2 = list2->next;
}
}
// At this point there will be exactly 1 empty list and 1 non-empty list.
// Link the non-empty list to the end of the list being built.
if (list1 != NULL) {
tail->next = list1;
} else {
tail->next = list2;
}
return head;
}