指针实现时间复杂度为O（n*logN）的排序算法（归并排序算法）

归并排序

 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