AC截图

题目

思路

1. 基本情况处理：

   • 如果链表为空 (head == NULL) 或者链表仅有一个节点 (head->next == NULL)，则链表已经是有序的，直接返回头节点 head。

2. 分割链表：

   • 使用快慢指针法找到链表的中间节点。slow 指针每次前进一格，而 fast 指针每次前进两格。当 fast 到达链表末尾时，slow 就会指向链表的中间位置。

   • 将链表从中间断开，分为左右两部分，并保存右半部分的起始节点 tmp。

3. 递归排序：

   • 对左半部分链表 head 和右半部分链表 tmp 分别递归调用 sortList 函数进行排序。

4. 合并有序链表：

   • 创建一个哑节点 h，其 next 指针用于构建新的有序链表。

   • 遍历两个已排序的子链表 left 和 right，比较当前节点值并将较小的节点添加到结果链表中。

   • 当其中一个子链表遍历完毕后，将另一个子链表剩下的节点直接连接到结果链表的末尾。

5. 返回结果：

   • 最终返回哑节点 res 的 next 指针所指向的节点，即排序后的链表头节点。

代码

/*** 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) {if(head==NULL || head->next==NULL)return head;ListNode *fast=head->next,*slow=head;while(fast!=NULL && fast->next!=NULL){slow = slow->next;fast = fast->next->next;}ListNode *tmp=slow->next;slow->next=NULL;ListNode *left = sortList(head);ListNode *right = sortList(tmp);ListNode *h = new ListNode(0);ListNode *res=h;while(left!=NULL && right!=NULL){if(left->val<right->val){h->next = left;left = left->next;}else{h->next = right;right = right->next;}h = h->next;}h->next = left!=NULL?left:right;return res->next;}
};