Skip to content

Instantly share code, notes, and snippets.

@clinyong
Created October 14, 2014 05:07
Show Gist options
  • Save clinyong/16b29bf7a0e3047acfc0 to your computer and use it in GitHub Desktop.
Save clinyong/16b29bf7a0e3047acfc0 to your computer and use it in GitHub Desktop.
链表的归并排序
/*归并排序*/
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment