leetcode Sort List

sort list: https://leetcode.com/problems/sort-list/

　　数组的排序比较相对于链表的，还是比较容易的。链表的排序，有一个最麻烦的地方就是，无法通过下标来访问节点，所以操作起来就没有数组那么方便。

　　链表排序，拿到这题，第一个想到的是快排。快排的思路和数组的一模一样，只不过要多两个list指针，一个指向比较节点的left，一个指向比较节点的right。从左往右遍历整个链表就可以了，快排过一次的链表，比较节点的位置都是正确地，然后用递归，排左边和右边，虽然有点麻烦，但还可以，思路比较简单。

 1 class Solution {
 2 public:
 3     ListNode* sortList(ListNode* head) {
 4         return sort(head, 0);
 5     }
 6     ListNode* sort(ListNode* head, ListNode* end)
 7     {   if(head == end)
 8             return head;
 9         ListNode* saveHead = head;
10         ListNode* preHead = NULL;
11         ListNode* lList = head;
12         ListNode* rList = head;
13         head=head->next;
14         while(head!= end ){
15             if(head->val > saveHead->val){
16                 rList->next = head;
17                 rList = rList->next;
18                 head = head->next;
19             }
20             else{
21                 ListNode* temphead = head->next;
22                 head->next = lList;
23                 lList= head;
24                 head = temphead;
25                 if(!preHead)
26                     preHead = lList;
27             }
28         }
29         rList->next =end;
30         if(preHead != NULL)
31             {
32                 preHead->next = saveHead;
33                lList = sort(lList, saveHead);
34             }
35         saveHead->next = sort(saveHead->next, end);
36         return lList;
37     }
38 };

　　这个结果，Time Limit Exceeded。

　　简直了，用的例子是节点的数字只有1,2,3，然后有几百个节点。快排的弊端，最坏情况下o(n2)的时间复杂度，马上体现出来了……

　　没办法，只有用归并排序了。归并的话最坏都是O(nlogn)的。

　　归并的话主要思路：首先，要把整个List，分成两个List，然后各自排序，在进行归并算法。两个子List，排序也是用归并，这里面的采用递归的方法。对子链表一直归并，知道子链表无法再分成两个链表为止。和数组的归并算法是一样的，只是数组的归并算法采用下表的方法来吧数组分成两个小数组，而链表，是真正把整个链表分开的。

　　这里主要用到两个子函数，split是把链表分成两个子链表，而merge是把两个有序链表进行归并排序。

 1 class Solution {
 2 public:
 3     ListNode* sortList(ListNode* head) {
 4         if(head==0 || head->next==0)
 5             return head;
 6         ListNode* mid = split(head);
 7         return merge(sortList(head), sortList(mid));
 8     }
 9     
10     ListNode* merge(ListNode* start1, ListNode* start2)
11     {
12         ListNode* head = 0;
13         if(start2 == 0)
14             return start1;
15         if(start1->val < start2->val)
16             {
17                 head = start1;
18                 start1 = start1->next;
19             }
20         else {
21             head = start2;
22             start2 = start2->next;
23         }
24         ListNode* tempList = head;
25         while(start1!= 0 && start2 != 0){
26             if(start1->val > start2->val){
27                 tempList->next = start2;
28                 start2 = start2->next;
29                 tempList = tempList->next;
30             }
31             else{
32                 tempList->next = start1;
33                 start1 = start1->next;
34                 tempList = tempList->next;
35             } 
36         }
37         if(start1 == 0)
38             tempList->next = start2;
39         else 
40             tempList->next = start1;
41         return head;
42     }
43     
44     ListNode* split(ListNode* head){
45         ListNode* fast = head;
46         ListNode* slow = head;
47         while(fast!= 0 && fast->next != 0 && fast->next->next !=0)
48         {
49             fast = fast->next->next;
50             slow = slow->next;
51         }
52         ListNode* midList = slow->next;
53         slow->next =0;
54         return midList;
55         
56     }
57 };

leetcode Sort List

推荐阅读