@Author: 张海拔
@Update: 2014-01-27
@Link: http://www.cnblogs.com/zhanghaiba/p/3534521.html
链表不像数组通过计算来随机存取，高效的排序算法如快速排序、堆排序都比较难实现，而归并排序就适合给链表排序。
在"有序单链表的合并 link(public)"问题中，我对带头结点和不带头结点的 有序单链表的合并算法做了比较全面的介绍。
而且知道就地合并算法比数组的合并算法时间效率更好，而且空间复杂度完胜，是O(1)（不然怎么叫就地）。
我们已经熟悉数组的“归并排序 link(public) ”，链表的归并排序用到的归并算法肯定是一样的，是典型的分治（二分）过程。
还是先给出伪代码：
merge_sort()
{
if 元素只有一个（已经有序）
return;
划分为左右两段
对左段进行merge_sort()
对右段进行merge_sort()
//此时左段和右端已经有序
对左段和右段进行sorted_merge()
}
sorted_list_merge()我们已经实现过了，merge_sort的思路也清晰了，剩下的问题，怎样把一段链表划分为两段？
链表的追及问题其实挺经典的，比如“链表是否有环”和“确定链表倒数第K个元素”，这样的问题都是用到追击（相对速度）的思路。
这里也一样，使用一个slow指针和一个fast指针，让fast指针相对slow指针的移动速度是单位1。这样fast走到尽头时,slow就在“中间”位置了。
这个时候需要考虑一些边界问题。
只有一个元素时，merge_sort()直接返回（已经有序，不用再处理），不再划分。
那么只有两个元素的情况对应划分的最小子问题——
首先，直接让slow初始指向first，而fast初始指向first->next，
然后每次前进让fast先后一步再验证是否到边界，若没有则fast和slow都走一步。
这样初始化后，fast走一步后发现到了边界，slow便不走，还是指向first。
将左段链表的首节点指针left = first，右段链表的首节点指针right = slow->next，然后切断原链表，即slow->next = NULL;
对于最小子问题这样划分是正确的（left指向第一个节点，right指向第二个节点）。
由于fast相对slow速度为1，且最小子问题也正确，对于更大的子问题，不管划分边界是[n/2]取上界还是下界问题都不大。
所以，这个算法时间复杂度仍然是O(n*lgn)，空间复杂度O(1)
数组的归并排序合并过程需要来回两次循环复制即2*O(n)，而链表的归并排序是划分过程仅需要循环一次1*O(n)。
两者递归的深度是一样的（都是二分）。
综合来看，链表归并排序的时间复杂度系数应该更低，即理论上会比数组归并排序更快。
下面给出链表归并排序的完整实现——
其中：
sorted_list_merge()是递归实现的
sorted_list_mrege2()是迭代实现的
list_merge_sort()接受带头结点的单链表，返回也是带头结点的单链表
list_merge_sort_core()接受不带头结点的单链表，返回的也是不带头结点的单链表
显然list_merge_sort()包装一下list_merge_sort_core()即可实现。
默认支持带头结点的单链表是考虑到问题集的其它链表都是带头结点的，而不带头结点适用性更强，实现了后者，前者只需简单包装就能实现。
另外约定：带头结点的单链表的头结点指针命名为head，而不带头结点的单链表的第一个结点（首节点）指针命名为first。带头节点的单链表的第一个有效元素的指针也叫first。
1 /* 2 *Author: ZhangHaiba 3 *Date: 2014-1-26 4 *File: merge_sort_for_singly_linked_list.c 5 * 6 *a demo shows merge sort for singly_linked_list 7 */ 8 9 #include <stdio.h> 10 #include <stdlib.h> 11 #define INF 0x7fffffff 12 13 typedef struct node * link; 14 typedef struct node { 15 int item; 16 link next; 17 }node; 18 19 //public 20 /* 21 *recieve a singly linked list with Head Node and 22 *return a singly linked list with Head Node as well 23 */ 24 link list_merge_sort(link list_head); 25 link NODE(int item, link next); 26 link list_create(int n); 27 void list_travel(link head); 28 void list_destroy(link head); 29 30 //private 31 /*recieve a singly linked list without Head Node and 32 *return a singly linked list without Head Node as well 33 */ 34 link list_merge_sort_core(link list_first); 35 void list_divide(link src_list, link *left_list, link *right_list); 36 link sorted_list_merge_in_place(link src_list_a, link src_list_b); //recusive 37 link sorted_list_merge_in_place2(link src_list_a, link src_list_b); //iterative 38 39 40 int main(void) 41 { 42 int n; 43 44 scanf("%d", &n); 45 link list_a = list_create(n); 46 printf("before merge sort, travel:\n"); 47 list_travel(list_a); 48 list_a = list_merge_sort(list_a); 49 printf("after merge sort, travel:\n"); 50 list_travel(list_a); 51 list_destroy(list_a); 52 return 0; 53 } 54 55 link list_merge_sort(link head) 56 { 57 if (head == NULL) //if [list with Head Node] have not Head Node 58 return NULL; 59 return NODE( INF, list_merge_sort_core(head->next) ); 60 } 61 62 link list_merge_sort_core(link first) //first node pointer 63 { 64 link left, right; 65 66 if (first == NULL || first->next == NULL) 67 return first; 68 list_divide(first, &left, &right); 69 left = list_merge_sort_core(left); 70 right = list_merge_sort_core(right); 71 return sorted_list_merge_in_place2(left, right); 72 } 73 74 //guarantee first != NULL 75 void list_divide(link first, link *left, link *right) 76 { 77 link slow = first, fast = first->next; 78 79 while (fast != NULL) { 80 fast = fast->next; 81 if (fast != NULL) { 82 fast = fast->next; 83 slow = slow->next; 84 } 85 } 86 *left = first; 87 *right = slow->next; 88 slow->next = NULL; 89 } 90 91 link sorted_list_merge_in_place(link left, link right) 92 { 93 if (left == NULL) 94 return right; 95 if (right == NULL) 96 return left; 97 link first = NULL; 98 if (left->item <= right->item) { 99 first = left; 100 first->next = sorted_list_merge_in_place(left->next, right); 101 } else { 102 first = right; 103 first->next = sorted_list_merge_in_place(left, right->next); 104 } 105 return first; 106 } 107 108 link sorted_list_merge_in_place2(link left, link right) 109 { 110 link tmp_head = NODE(INF, NULL); 111 link first = tmp_head; 112 113 for (; left != NULL && right != NULL; first = first->next) { 114 if (left->item <= right->item) 115 first->next = left, left = left->next; 116 else 117 first->next = right, right = right->next; 118 } 119 first->next = left != NULL ? left : right; 120 first = tmp_head->next; 121 free(tmp_head); 122 return first; 123 } 124 125 126 link NODE(int item, link next) 127 { 128 link born = malloc(sizeof (node)); 129 born->item = item; 130 born->next = next; 131 return born; 132 } 133 134 //tail insert 135 link list_create(int n) 136 { 137 int i, item; 138 link head = NODE(INF, NULL); 139 link tail = head; 140 141 for (i = 0; i < n; ++i) { 142 scanf("%d", &item); 143 tail->next = NODE(item, NULL); 144 tail = tail->next; 145 } 146 return head; 147 } 148 149 void list_travel(link head) 150 { 151 for (head = head->next; head != NULL; head = head->next) 152 printf(head->next == NULL ? "%d\n" : "%d ", head->item); 153 } 154 155 void list_destroy(link head) 156 { 157 head->next == NULL ? free(head) : list_destroy(head->next); 158 }
测试示范：
ZhangHaiba-MacBook-Pro:code apple$ ./a.out 1 435 before merge sort, travel: 435 after merge sort, travel: 435 ZhangHaiba-MacBook-Pro:code apple$ ./a.out 9 4324 31 515 41 46 43 8 53 3 before merge sort, travel: 4324 31 515 41 46 43 8 53 3 after merge sort, travel: 3 8 31 41 43 46 53 515 4324