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

用歸并排序

歸并排序（O(nlogn)），非原地排序（額外申請空間）

堆排序（O(nlogn)），原地排序

快排（期望:O(nlogn)，最壞O(n2)），原地排序

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode *sortList(ListNode *head) {if(head == NULL) return head;if(head -> next == NULL){return head;}ListNode* fast = head;ListNode* slow = head;while(fast -> next != NULL && fast -> next -> next != NULL){fast = fast -> next;fast = fast -> next;slow = slow -> next;}ListNode* mid = slow -> next;slow -> next = NULL;ListNode* list1 = sortList(head);ListNode* list2 = sortList(mid);ListNode* sorted = merge(list1 , list2);return sorted;}ListNode* merge(ListNode* list1 , ListNode* list2){if(list1 == NULL) return list2;if(list2 == NULL) return list1;ListNode* head;ListNode* tmp;if(list1 -> val < list2 -> val){head = list1;list1 = list1 -> next;}else{head = list2;list2 = list2 -> next;}tmp = head;while(list1 != NULL && list2 != NULL){if(list1 -> val < list2 -> val){tmp -> next = list1;tmp = list1;list1 = list1 -> next;}else{tmp -> next = list2;tmp = list2;list2 = list2 -> next;}}if(list1 != NULL) tmp -> next = list1;if(list2 != NULL) tmp -> next = list2;return head;} };

總結(jié)

以上是生活随笔為你收集整理的Sort List的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。