归并排序--数组和链表的实现
数组实现
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;}