【面试】单链表排序，时间复杂度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;
}