AC截图
题目
思路
-
基本情况处理：
-
如果链表为空 (
head == NULL) 或者链表仅有一个节点 (head->next == NULL)，则链表已经是有序的，直接返回头节点head。
-
-
分割链表：
-
使用快慢指针法找到链表的中间节点。
slow指针每次前进一格，而fast指针每次前进两格。当fast到达链表末尾时，slow就会指向链表的中间位置。 -
将链表从中间断开，分为左右两部分，并保存右半部分的起始节点
tmp。
-
-
递归排序：
-
对左半部分链表
head和右半部分链表tmp分别递归调用sortList函数进行排序。
-
-
合并有序链表：
-
创建一个哑节点
h，其next指针用于构建新的有序链表。 -
遍历两个已排序的子链表
left和right，比较当前节点值并将较小的节点添加到结果链表中。 -
当其中一个子链表遍历完毕后，将另一个子链表剩下的节点直接连接到结果链表的末尾。
-
-
返回结果：
-
最终返回哑节点
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;}
};
