我們可以試用歸并排序解決：
對鏈表歸并排序的程序如下，
找到鏈表的中點，以中點為分界，將鏈表拆分成兩個子鏈表，尋找鏈表的中點可以使用快慢指標的做法，快指標每次移動 2 步，慢指標每次移動 1步，當快指標到達鏈表末尾時，慢指標指向的鏈表節點即為鏈表的中點，
對兩個子鏈表分別排序，
將兩個排序后的子鏈表合并，得到完整的排序后的鏈表
上述程序可以通過遞回實作，遞回的終止條件是鏈表的節點個數小于或等于 1，即當鏈表為慷訓者鏈表只包含 1 個節點時，不需要對鏈表進行拆分和排序，
class Solution {
public:
ListNode* sortList(ListNode* head) {
return sortList(head, nullptr);
}
ListNode* mergesort(ListNode* head, ListNode* tail) {
if (head == nullptr) {
return head;
}
if (head->next == tail) {
head->next = nullptr;
return head;
}
ListNode* slow = head, * fast = head;
while (fast != tail) {
slow = slow->next;
fast = fast->next;
if (fast != tail) {
fast = fast->next;
}
}
return merge( mergesort(head, slow), mergesort(slow, tail));
}
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummyHead = new ListNode(0);
ListNode* temp = dummyHead, * temp1 = head1, * temp2 = head2;
while (temp1 != nullptr && temp2 != nullptr) {
if (temp1->val <= temp2->val) {
temp->next = temp1;
temp1 = temp1->next;
}
else {
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if (temp1 != nullptr) {
temp->next = temp1;
}
else if (temp2 != nullptr) {
temp->next = temp2;
}
return dummyHead->next;
}
};
快速排序不能隨機選取節點，時間復雜度太高所以會超時
class Solution {
public static ListNode sortList(ListNode head) {
return quickSort(head ,null);
}
public static ListNode quickSort(ListNode head ,ListNode end){
if(head ==end || head.next ==end) return head;
ListNode lhead = head ,utail = head ,p = head.next;
while (p != end){
ListNode next = p.next;
if(p.val < head.val){//頭插
p.next = lhead;
lhead = p;
}
else { //尾插
utail.next = p;
utail = p;
}
p = next;
}
utail.next = end;
ListNode node = quickSort(lhead, head);
head.next = quickSort(head.next, end);
return node;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277767.html
標籤：其他
下一篇：JAVA I/0流學習筆記