OJ题之单链表排序
描述
给定一个节点数为n的无序单链表，对其按升序排序。
数据范围：0<n≤1000000<n≤100000，保证节点权值在[−109,109][−109,109]之内。
要求：空间复杂度 O(n)，时间复杂度 O(nlogn)
给出以下三种方式：
1. 冒泡排序
通过重复遍历链表，比较相邻元素并交换位置，直到整个链表有序。
void bubbleSort(ListNode* head) {if (!head) return;bool swapped;do {swapped = false;ListNode* current = head;while (current->next) {if (current->val > current->next->val) {std::swap(current->val, current->next->val);swapped = true;}current = current->next;}} while (swapped);
}
2. 选择排序
每次遍历链表找到最小元素，将其与当前元素交换位置。
void selectionSort(ListNode* head) {for (ListNode* current = head; current; current = current->next) {ListNode* minNode = current;for (ListNode* nextNode = current->next; nextNode; nextNode = nextNode->next) {if (nextNode->val < minNode->val) {minNode = nextNode;}}std::swap(current->val, minNode->val);}
}
3. 合并排序
采用分治法，将链表分成两半，递归地排序每一半，然后合并两个已排序的链表。
ListNode* merge(ListNode* l1, ListNode* l2) {ListNode dummy(0);ListNode* tail = &dummy;while (l1 && l2) {if (l1->val < l2->val) {tail->next = l1;l1 = l1->next;} else {tail->next = l2;l2 = l2->next;}tail = tail->next;}tail->next = l1 ? l1 : l2;return dummy.next;
}ListNode* mergeSort(ListNode* head) {if (!head || !head->next) return head;ListNode* slow = head;ListNode* fast = head->next;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}ListNode* mid = slow->next;slow->next = nullptr;return merge(mergeSort(head), mergeSort(mid));
}