目录

148.排序链表

题目描述

题目链接

解题思路与代码

---

==============================================================

148.排序链表

题目描述

给你链表的头结点 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 = []
输出：[]

题目链接

148.排序链表

解题思路与代码

本题目思路是使用归并排序，不过是链表的实现方法。我们来通过图详解递归思路

slow和fast作用就是分割链表，如下图。

然后我们让tem = slow->next

slow ->next = NULL。

分割成如下。

递归传递head和tem ，然后递归终止条件就是 ：

传递的值是NULL或者只有一个结点。

排序逻辑就是新建一个虚拟头结点，将传递的这些结点进行正常排序比较。如图：

最后head1 ->next返回，head2 ->next也返回。

这返回的两个链表继续比较。

最后返回nhead->next就是最终结果。

其实就是归并排序，只不过链表实现而已。

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