链表的归并排序

merge_sort_list.c

/*归并排序*/  
void MergeSort(struct node** headRef)  
{  
    struct node* head = *headRef;  
    struct node* a;  
    struct node* b;  
  
    /*base case-- length 0 or 1 */  
    if((head == NULL) || (head->next == NULL))  
    {  
        return;  
    }  
      
    /*Split head into 'a' and 'b' sublists */  
    FrontBackSplit(head, &a, &b);  
  
    /*Recursively sort the sublists */  
    MergeSort(&a);  
    MergeSort(&b);  
  
    /* answer = merge the two sorted lists together */  
    *headRef = SortedMerge(a, b);  
}  
  
/*合并*/
struct node* SortedMerge(struct node* a, struct node* b)  
{  
    struct node* result = NULL;  
  
    /* Base cases */  
    if(a == NULL)  
        return (b);  
    else if(b == NULL)  
        return (a);  
  
    /* Pick either a or b recur */  
    if(a->data <= b->data)  
    {  
        result = a;  
        result->next = SortedMerge(a->next, b);  
    }  
    else  
    {  
        result = b;  
        result->next = SortedMerge(a, b->next);     
    }  
    return (result);  
}  
  
/* 设置两个指针，一个步长为1， 一个步长为2，当快指针到达尾结点时，慢指针指向中间结点。 */  
void FrontBackSplit(struct node* source, struct node** frontRef, struct node** backRef)  
{  
    struct node* fast;  
    struct node* slow;  
  
    if(source == NULL || source->next == NULL)  
    {  
        *frontRef = source;  
        *backRef = NULL;  
    }  
    else  
    {  
        slow = source;  
        fast = source->next;  
  
        /* Advance 'fast' two nodes, and advance 'slow' one node */   
        while(fast != NULL)  
        {  
            fast = fast->next;  
            if( fast != NULL )  
            {  
                slow = slow->next;  
                fast = fast->next;  
            }  
        }  
  
        *frontRef = source;  
        *backRef = slow->next;  
        slow->next = NULL;  
    }  
}