Sort List

一、插入排序（InsertionSortList）

单链表的插入排序，折腾了好久一会儿，好不容易做出来，在leetcode上仅仅击败百分之十几的人，而且代码啰嗦，参考了下别人代码，提交了下面的代码接近50%

 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* insertionSortList(ListNode* head) {
12         if(head == nullptr)  return head;
13         if(head->next == nullptr) return head;
14 
15         ListNode* helper = new ListNode(-1);
16         
17         ListNode* cur= head;
18         ListNode* pre;
19         ListNode* next;
20 
21         while(cur){
22             next = cur->next;
23             pre = helper;
24             
25             while(pre->next != nullptr && pre->next->val < cur->val){
26                 pre = pre -> next;
27             }
28             
29             cur->next = pre->next;
30             pre->next = cur;
31             cur = next;
32         }
33         
34         head = helper->next;
35         delete helper;
36         return head;
37     }
38 };

二、归并排序（相比上述的InsertionSortList,单链表的归并排序，时间复杂度为nlog(n)，但是小数据两的排序，插入排序更好

 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         if(head == nullptr || head->next == nullptr)  return head;
13         
14         ListNode* fast = head;
15         ListNode* slow = head;
16         while(fast->next != nullptr && fast->next->next != nullptr){
17             fast = fast->next->next;
18             slow = slow->next;
19         }
20         fast = slow;
21         slow = slow->next;
22         fast->next = nullptr;
23         
24         ListNode* L1 = sortList(head);
25         ListNode* L2 = sortList(slow);
26         
27         return mergeTwoLists(L1,L2);
28     }
29 private:
30     ListNode* mergeTwoLists(ListNode* l1,ListNode* l2){
31         if(l1 == nullptr)  return l2;
32         if(l2 == nullptr)  return l1;
33         
34         ListNode* head = new ListNode(-1);
35         ListNode* p = head;
36         while(l1 && l2)
37         {
38             if(l1->val < l2->val){
39                 p->next = l1;
40                 l1 = l1-> next;
41                 p = p->next;
42             }else{
43                 p->next = l2;
44                 l2 = l2->next;
45                 p = p->next;
46             }
47         }
48         if(l1)  p->next = l1;
49         else  p->next = l2;
50         p = head->next;
51         delete head;
52         return p;
53      } 
54 };