归并排序--数组和链表的实现

数组实现

struct node{    int data;    node * next;};/***对两个有序链表进行归并*/node *MergeList(node *head1, node *head2){    node * tmp;    if(head1 == NULL)      return head2;    if(head2 == NULL)      return head1;    if(head1->data < head2->data)    {      tmp = head1;      head1 = head1->next;    }    else    {      tmp = head2;      head2 = head2->next;    }    tmp->next = MergeList(head1, head2);    return tmp;}/***归并排序，参数为要排序的链表的头结点，函数返回值为排序后的链表的头结点*/node *MergeSort(node *head){    if(head == NULL)      return 0;    node * r_head = head;    node *head1 = head;    node* head2 = head;    while(head2->next != NULL && head2->next ->next!= NULL)    {      head1 = head1->next;      head2 = head2->next->next;    }    if(head1->next == NULL)/*说明只有一个节点，则返回该节点*/      return r_head;    head2 = head1->next;    head1->next = NULL;    head1 = head;    /*函数MergeList是对两个有序链表进行归并，返回值是归并后的链表的头结点*/    r_head = MergeList(MergeSort(head1), MergeSort(head2));    return r_head;}