【面试】单链表排序，时间复杂度O(nlogn)、空间复杂度O(1)

(1)如果不要求空间复杂度，则可以将链表元素存至$vector$，排序后将其化为链表

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct ListNode {
    int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {
    }
};
int main() {
    int n;cin >> n;vector<int> ans(n);for (int i = 0; i < n; ++i) {
    cin >> ans[i];}sort(ans.begin(), ans.end());ListNode *head = new ListNode(0);ListNode *cur = head;for (int i = 0; i < n; ++i) {
    ListNode *temp = new ListNode(ans[i]);cur->next = temp;cur = temp;}head = head->next;while (head) {
    if (head->next) cout << head->val << "->";else cout << head->val << endl;head = head->next;}return 0;
}

(2) 现在要求空间复杂度为$O(1)$，那么我们可以采用归并排序进行处理

• 使用快慢指针找到中间节点，然后递归进行归并

#include <iostream>
using namespace std;
struct ListNode {
    int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {
    }
};ListNode *Merge(ListNode* left, ListNode* right) {
    if (left == nullptr && right == nullptr) return nullptr;ListNode p(0);ListNode *h = &p;while (left && right) {
    if (left->val < right->val) {
    h->next = left; left = left->next;}else {
    h->next = right; right = right->next;}h = h->next;}if (left && !right) h->next = left;if (!left && right) h->next = right;return p.next;
}ListNode *SortList(ListNode *head) {
    if (head == nullptr || head->next == nullptr) return head;ListNode *fast = head->next;ListNode *slow = head;while (fast && fast->next) {
    slow = slow->next;fast = fast->next->next;}ListNode *left = SortList(slow->next);slow->next = nullptr;ListNode *right = SortList(head);return Merge(left, right);
}int main() {
    int n;cin >> n;ListNode *head = new ListNode(0);ListNode *cur = head;for (int i = 0; i < n; ++i) {
    int num;cin >> num;ListNode *temp = new ListNode(num);cur->next = temp;cur = temp;}head = SortList(head->next);while (head) {
    if (head->next)cout << head->val << "->";else cout << head->val;head = head->next;}return 0;
}