2024/9/23 leetcode 148题 排序链表
目录
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;}
};