在C++中使用歸并排序處理鏈表排序的步驟如下:
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* mergeSort(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
// 快慢指針找中點
ListNode* fast = head;
ListNode* slow = head;
ListNode* prev = nullptr;
while (fast != nullptr && fast->next != nullptr) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr; // 斷開鏈表
ListNode* left = mergeSort(head);
ListNode* right = mergeSort(slow);
return merge(left, right);
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1 != nullptr) {
cur->next = l1;
} else {
cur->next = l2;
}
return dummy->next;
}
ListNode* sortList(ListNode* head) {
return mergeSort(head);
}
通過以上步驟,就可以在C++中實現歸并排序對鏈表進行排序。