#include
#include "tool.c"
#define NULL ((void *)0)
struct LinkList{
struct LinkList *next;
int value;
} *linkList,node;
/*
try to mergeSort a linkList
*/
int main(){
void printLinkList(struct LinkList *list);
struct LinkList *mergeSort(struct LinkList *head);
//build a linkList,end with an NULL node
struct LinkList *list=(struct LinkList *)malloc(sizeof(node));
struct LinkList *current=list;
int i;
for(i=0;i<20;i++){
struct LinkList *temp=(struct LinkList *)malloc(sizeof(node));
temp->value=getRandom();
current->next=temp;
current=current->next;
}
current->next=NULL;
printf("Before sort:\n");
printLinkList(list->next);
//mergeSort the list.
resList=mergeSort(list->next);
printf("After sort:\n");
printLinkList(list->next);
getchar();
return 0;
}
/*
Mergesort the linkList.
*/
struct LinkList *mergeSort(struct LinkList *head){
struct LinkList *merge(struct LinkList *first,struct LinkList *second);
struct LinkList *first;
struct LinkList *second;
first=head;
second=head;
if(first==NULL||first->next==NULL){
//Note here is the place that can jump out of the recursion.
return first;
}
//cut the LinkList into 2 list,one lead by "first",the other lead by "second".
while(second->next!=NULL && second->next->next!=NULL){
first=first->next;
second=second->next->next;
}
if(first->next!=NULL){
second=first->next;
first->next=NULL;
first=head;
}
//merge the List.
return merge(mergeSort(first),mergeSort(second));
}
/*
Merge the list.
It is quite similar with the operation of the merge of Array,
but note that because of the linklist,we avoid the large space expence of the
usual merge of array.
*/
struct LinkList *merge(struct LinkList *first,struct LinkList *second){
struct LinkList *resList=(struct LinkList *)malloc(sizeof(node));
struct LinkList *current;
current=resList;
while(first!=NULL && second!=NULL){
if(first->value<=second->value){
current->next=first;
current=current->next;
first=first->next;
}else{
current->next=second;
current=current->next;
second=second->next;
}
}
while(first!=NULL){
current->next=first;
current=current->next;
first=first->next;
}
while(second!=NULL){
current->next=second;
current=current->next;
second=second->next;
}
return resList->next;
}
/*
Print the LinkList.
*/
void printLinkList(struct LinkList *list){
while(list!=NULL){
printf("%d ",list->value);
list=list->next;
}
printf("\n");
}
