本文共 4199 字，大约阅读时间需要 13 分钟。
递归解法：本来mergesort需要O(n)的空间复杂度，但这里是链表，所以只需要O(1)的空间复杂度
要求时间复杂度为O(nlogn)，那么不能用quickSort了（最坏O(n^2)），所以使用mergeSort.
通常写排序算法都是基于数组的，这题要求基于链表。所以需要自己设计函数获得middle元素，从而进行切分。
参考Linked List Cycle II中的“龟兔赛跑”思想：兔子前进两步，龟前进一步，从而可以获得middle元素
注意获取中间节点：需要三个指针：fast slow pre（pre指向slow的上一个位置，可以举两个节点的例子进行带入考虑，如果不适用pre会出错）
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* sortList(ListNode* head) { if(head == NULL || head->next == NULL) return head; ListNode *middle = getMiddle(head); ListNode *head2 = middle->next; middle->next = NULL; return merge(sortList(head),sortList(head2)); } ListNode *getMiddle(ListNode *head){ ListNode *fast = head,*slow = head,*pre = NULL; while(fast && fast->next){ fast = fast->next->next; pre = slow; slow = slow->next; } return pre; } ListNode *merge(ListNode *first,ListNode *second){ if(first == NULL) return second; if(second == NULL) return first; ListNode helper(0); ListNode *work = &helper; while(first && second){ if(first->val <= second->val){ work->next = first; first = first->next; }else{ work->next = second; second = second->next; } work = work->next; } if(first) work->next = first; if(second) work->next = second; return helper.next; }};
参考：http://www.cnblogs.com/ganganloveu/p/3763707.html
非递归解法：
Nice problem. I use a non-recurisve way to write merge sort. For example, the size of ListNode is 8,
Round #1 block_size = 1
(a1, a2), (a3, a4), (a5, a6), (a7, a8)
Compare a1 with a2, a3 with a4 ...
Round #2 block_size = 2
(a1, a2, a3, a4), (a5, a6, a7, a8)
merge two sorted arrays (a1, a2) and (a3, a4), then merge tow sorted arrays(a5, a6) and (a7, a8)
Round #3 block_size = 4
(a1, a2, a3, a4, a5, a6, a7, a8)
merge two sorted arrays (a1, a2, a3, a4), and (a5, a6, a7, a8)
No need for round #4 cause block_size = 8 >= n = 8
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution{public: ListNode *sortList(ListNode *head){ if(head == NULL || head->next == NULL) return head; int n = countList(head),iter = 0,blockSize = 1,a = 0,b = 0; ListNode *A,*B,*it,*last,*tmp; ListNode helper(0); //排序可能会打乱第一个结点（head）的顺序，所以需要一个辅助节点 last = &helper; last->next = head; while(blockSize < n){ iter = 0; it = helper.next; last = &helper; //last为排序时候的工作节点 while(iter < n){ a = min(n - iter,blockSize); b = min(n - iter - a,blockSize); A = it; //待排序的第一个块的第一个结点 if(b != 0){ for(int i = 0; i < a - 1; i++) it = it->next; B = it->next; it->next = NULL; it = B; //待排序的第二个块（和A相邻的块）的第一个结点 for(int j = 0; j < b - 1; j++) it = it->next; tmp = it->next; it->next = NULL; it = tmp; } while(A || B){ if(B == NULL || ( A != NULL && A->val <= B->val)){ last->next = A; A = A->next; }else{ last->next = B; B = B->next; } last = last->next; } last->next = NULL; iter += a + b; //iter为已经排序的节点个数 } blockSize <<= 1; } return helper.next; } int countList(ListNode *head){ int n = 0; while(head){ n++; head = head->next; } return n; }}; 参考：https://leetcode.com/discuss/10264/my-o-n-log-n-time-o-1-space-solution