一.题目要求

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

二.题目难度

中等

三.输入样例

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]

四.解题思路

解法1：用map按值大小存结点
解法2：归并排序(GPT)

五.代码实现

解1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        map<int,vector<ListNode*>> nodeMap;
        while(head)
        {
            nodeMap[head->val].push_back(head);
            head = head->next;
        }
        ListNode* p = dummy;
        for(auto node : nodeMap)
        {
            for(vector<ListNode*>::iterator it = node.second.begin(); it != node.second.end(); it++)
                {
                    (*it)->next = nullptr;
                    p->next = *it;
                    p = p->next;
                }
        }
        return dummy->next;
    }
};

解2

class Solution {
public:
    ListNode* sortList(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;  // 分割链表

        // 递归排序左右两部分
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);

        // 合并排序后的链表
        return merge(left, right);
    }

private:
    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;
    }
};

六.题目总结

归并排序在链表排序中非常有效，因为它可以利用链表的节点指针操作，无需像数组那样进行大量的元素交换，其时间复杂度是 $O(nlogn)$，但通常比基于 std::map 的方法更快，因为它具有更好的常数因子和较低的内存使用。

递归分析：

class Solution {
public:
    ListNode* sortList(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;  // 分割链表

        // 传给下一层继续分割
        //直到分割到不能再分开始合并
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);

        // 合并排序后的链表
        return merge(left, right);
    }