LeetCode--HOT100题（33）

题目描述：148. 排序链表（中等）

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

LeetCode做题链接：LeetCode-排序链表

示例 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(nlog n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

题目接口

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {}
}

解题思路

参考题解：Sort List （归并排序链表）

思路：递归

• 1.用二分法的方法将列表从中间分割，再把分割的列表继续从中间分割，分割到最小单位（快慢指针）
• 2.递归终止条件： 当 head.next == None 时，说明只有一个节点了，直接返回此节点
• 3.再返回两个分割列表的合并列表（合并有序列表）
  可以跟着这个图理解一下~
  

代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {// 1、递归结束条件if (head == null || head.next == null) {return head;}// 2、找到链表中间节点并断开链表 & 递归下探ListNode midNode = middleNode(head);ListNode rightHead = midNode.next;// 截断列表midNode.next = null;// 递归，不断下探到最深出最低端，再合并返回ListNode left = sortList(head);ListNode right = sortList(rightHead);// 3、当前层业务操作（合并有序链表）return mergeTwoLists(left, right);}//  找到链表中间节点（876. 链表的中间结点）private ListNode middleNode(ListNode head) {if (head == null || head.next == null) {return head;}ListNode slow = head;ListNode fast = head.next.next;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}// 合并两个有序链表（21. 合并两个有序链表）private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode sentry = new ListNode(-1);ListNode curr = sentry;while(l1 != null && l2 != null) {if(l1.val < l2.val) {curr.next = l1;l1 = l1.next;} else {curr.next = l2;l2 = l2.next;}curr = curr.next;}curr.next = l1 != null ? l1 : l2;return sentry.next;}
}

PS:

感谢您的阅读！如果您觉得本篇文章对您有所帮助，请给予博主一个赞喔~