题目如下：（）

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, as13         // the same Solution instance will be reused for each test case.14         //链表归并排序15         if(head == NULL || head->next == NULL)return head;16         else17         {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 one35     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             else53             {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 };

【版权声明】转载请注明出处：