题目
给你链表的头结点 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 = []
输出：[]提示：
- 链表中节点的数目在范围
[0, 5 * 104]内 -105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
解答
- 为了解题而解题的解法
建立一个动态数组nodes，将链表中的每个元素放入动态数组中，然后使用sort排序，接着将动态数组进行遍历，将每个数字新建一个节点放入结果链表中，C++代码实现如下：
/**
* 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) {
vector<int> nodes;
while (head != nullptr) {
nodes.push_back(head->val); // 将链表的每个节点的值放入动态数组中
head = head->next;
}
sort(nodes.begin(), nodes.end()); // 对动态数组中的元素进行排序
ListNode* sortedList = nullptr;
ListNode** cur = &sortedList; // 定义一个指向指针的指针 cur
for (auto node_num: nodes) {
*cur = new ListNode(node_num); // 将排序好的数字加入新链表中
cur = &((*cur)->next);
}
return sortedList; // 返回链表头节点
}
};这段代码涉及了指针和地址的操作，可以解读为：
ListNode** cur：定义一个指向指针的指针 cur
&sortedList：获取 sortedList 的地址，也就是一个指向指针 sortedList 的指针
cur = &sortedList：将 sortedList 的地址赋值给 cur，此时 cur 指向 sortedList 的指针
这样做的目的是为了可以更改 sortedList 的指针，从而修改链表结构。在 for 循环中，*cur 表示指针 cur 所指向的指针，即 sortedList 的指针，将新的节点插入到 sortedList 后，cur 需要指向插入节点的 next 指针，因此使用了 cur = &((*cur)->next) 的写法。
- 归并排序
归并排序的思路如下：利用快慢指针将链表分为左链表和右链表，分而治之，将分得的两个链表进行再一次分割和归并，最终归并得到结果。
class Solution {
public:
// 归并排序
ListNode* sortList(ListNode* head) {
// 如果链表为空或只有一个节点，直接返回
if (head == nullptr || head->next == nullptr) return head;
// 找到链表的中点，用快慢指针法
ListNode* slow = head; // 慢指针，每次走一步
ListNode* fast = head->next; // 快指针，每次走两步
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next; // 慢指针走到中点
fast = fast->next->next; // 快指针走到末尾或者null
}
// 将链表从中点断开为两个子链表
ListNode* mid = slow->next;
slow->next = nullptr;
// 对左右子链表分别进行排序
ListNode* left = sortList(head);
ListNode* right = sortList(mid);
// 合并两个有序的子链表为一个有序的链表
return mergeTwoLists(left, right);
}
// 合并两个有序的链表为一个有序的链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 创建一个哑节点作为合并后链表的头结点
ListNode dummy(0);
// 创建一个指针cur指向当前合并后链表的最后一个节点，初始为哑节点
ListNode* cur = &dummy;
// 当l1和l2都不为空时，比较它们的值，将较小的值接在cur后面，并更新对应的指针
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;
}
// 当l1或l2有一个为空时，直接将另一个非空的链表接在cur后面即可
if (l1 != nullptr) cur->next = l1;
if (l2 != nullptr) cur->next = l2;
return dummy.next; // 返回哑节点的下一个节点，即合并后链表的头结点
}
};