利用归并实现 链表排序

   

    之前就听说可以用归并来实现链表的排序,刚听到还楞了一下,觉得主要问题是归并数组时需要不断地对数组进行二分,这种操作对于数组直接利用下标即可定位,可是链表定位元素就很麻烦了,不知道怎么实现,后来看了一下,二分的操作果然,当然还是得利用循环,不过相当巧妙,是使用两个步长一快一慢的指针进行,也算奇思妙想,代码如下,重点部位有注释(英文是因为代码里注释习惯写英文,避免之后因为编码问题,辛辛苦苦的注释全部变成圈圈框框,见谅):

 

#include <stdio.h>
#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");
}

 

 

    值得一提的是,链表排序和归并比较天作之合的一点是,归并在保留了nLg(n)的时间复杂度的同时,还避开了一般比如数组归并时的的额外空间开销,注意merge() 函数的操作.

    数组归并时,在合并子数组时,需要先开出额外空间,存储两个子数组的合并结果,然后再写到原数组中.

    而这里呢,链表的合并只需开一个头结点,然后让它随着两个子链表不断修改指向即可.

    所以说是天作之合,毫不夸张.

 

    ps1.关于数组的归并实现,可以参考这里:http://mmliu.iteye.com/blog/683375

    ps2.至于链表的归并实现,参考了这里,可以看看:http://topic.csdn.net/u/20071210/13/673b1e16-d788-402f-a06d-84c4808434ef.html