归并排序
1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9 class Solution {
10 public:
11 ListNode* sortList(ListNode* head) {
12 //排序算法 空间复杂度N*logN
13 //归并排序
14 if(!head||!(head->next)){
15 return head;
16 }
17 ListNode* slow = head;
18 //让slow比最终的位置慢一步
19 ListNode* fast = head->next;
20 ListNode* temp;
21 while(fast&&(fast->next)){
22 if(fast->next->next){
23 slow = slow->next;
24 fast = fast->next->next;
25 }else{
26 //slow = slow->next;
27 fast = fast->next;
28 }
29
30 }
31 //将前半段的与后半段分开
32 temp = slow;
33 slow = slow->next;
34 temp->next = NULL;
35 // return head;
36 return Merge(sortList(head),sortList(slow));
37 }
38 ListNode* Merge(ListNode* L1,ListNode* L2){
39 ListNode cur(0);
40 ListNode* temp = &cur;
41 while(L1&&L2){
42 if((L1->val)<=(L2->val)){
43 temp->next = L1;
44 L1 = L1->next;
45 }else if((L1->val)>(L2->val)){
46 temp->next = L2;
47 L2 = L2->next;
48 }
49 temp = temp->next;
50 }
51 if(L1){
52 temp->next = L1;
53 }else{
54 temp->next = L2;
55 }
56 return cur.next;
57 }
58 };
实现过程
归并排序算法：
1、首先将链表进行切分。在我们的算法中，使用两个指针fast和slow,fast的遍历速度是slow指针的两倍。所以当fast遍历到链表的末尾时，slow恰好找到了链表的最中间位置，（这是使用链表存储相对于数组比较麻烦的地方，没办法直接选取最中间的值）。
2、使用head和slow将链表分成两个子链表，然后继续1中操作，将子链表再分成两部分。直到每个子链表只含有一个元素为止。
3、然后我们将两个子链表进行合并，生成含有2个元素排好序的链表，再将含有2个元素的子链表合并生成4个元素的链表。。。以此类推直到生成一个排好序的新链表。
注意：合并两个都排好序的链表时，我们只需要遍历一遍，时间复杂度为O（N）。
例如：
7 -> 3 -> 9 -> 6 -> 2 -> 8 -> 4 -> 1 -> null
\ / \ / \ / \ /
3->7->null 6->9->null 2->8->null 1->4->null
\ / \ /
3->6->7->9->null 1->2->4->8->null
\ /
1->2->3->4->6->7->8->9->null