LeetCode:Sort List

题目如下：（题目链接）

Sort a linked list in O(n log n) time using constant space complexity.

在上一题中使用了插入排序，时间复杂度为O(n^2)。nlogn的排序有快速排序、归并排序、堆排序。双向链表用快排比较适合，堆排序也可以用于链表，单向链表适合用归并排序。以下是用归并排序的代码：本文地址

 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         // IMPORTANT: Please reset any member data you declared, as
13         // the same Solution instance will be reused for each test case.
14         //链表归并排序
15         if(head == NULL || head->next == NULL)return head;
16         else
17         {
18             //快慢指针找到中间节点
19             ListNode *fast = head,*slow = head;
20             while(fast->next != NULL && fast->next->next != NULL)
21             {
22                 fast = fast->next->next;
23                 slow = slow->next;
24             }
25             fast = slow;
26             slow = slow->next;
27             fast->next = NULL;
28             fast = sortList(head);//前半段排序
29             slow = sortList(slow);//后半段排序
30             return merge(fast,slow);
31         }
32         
33     }
34     // merge two sorted list to one
35     ListNode *merge(ListNode *head1, ListNode *head2)
36     {
37         if(head1 == NULL)return head2;
38         if(head2 == NULL)return head1;
39         ListNode *res , *p ;
40         if(head1->val < head2->val)
41             {res = head1; head1 = head1->next;}
42         else{res = head2; head2 = head2->next;}
43         p = res;
44         
45         while(head1 != NULL && head2 != NULL)
46         {
47             if(head1->val < head2->val)
48             {
49                 p->next = head1;
50                 head1 = head1->next;
51             }
52             else
53             {
54                 p->next = head2;
55                 head2 = head2->next;
56             }
57             p = p->next;
58         }
59         if(head1 != NULL)p->next = head1;
60         else if(head2 != NULL)p->next = head2;
61         return res;
62     }
63 };