Leetcode 排序链表

这段代码的算法思想是 归并排序，一种适合链表的排序方法。它通过递归地将链表拆分成两部分，分别排序，然后合并已排序的部分，从而达到整体排序的目的。以下是代码的中文解释：

算法步骤：

1. 找到链表的中点：

   • 在 getMid 方法中，使用了快慢指针（slow 和 fast 指针）来找到链表的中间节点。
   • fast 指针每次移动两步，slow 指针每次移动一步。当 fast 指针到达链表末尾时，slow 指针刚好位于链表中间。
   • 将链表分为左右两部分，slow 为中间节点，从而将链表一分为二。

2. 递归地排序两部分链表：

   • sortList 方法中，通过递归地对左半部分和右半部分链表进行排序。递归的终止条件是链表为空或只有一个节点，这时链表已是有序的。
   • 对左右两部分链表分别调用 sortList 方法，进行递归排序，最终会得到两个已排序的子链表。

3. 合并两个有序链表：

   • merge 方法用于合并两个已排序的链表，使用的是“归并”的思想。
   • 创建一个虚拟节点 dummy 来帮助合并，将指针 current 初始化为 dummy。
   • 遍历两个链表 left 和 right，比较当前节点的值，将较小的节点连接到 current 节点的后面，然后移动指针。
   • 最后，将剩余的节点（若有）连接到合并后的链表末尾。
   • dummy.next 即为合并后有序链表的头节点。

代码的时间复杂度和空间复杂度：

• 时间复杂度：归并排序的时间复杂度为 (O(n \log n))，其中 (n) 是链表的节点数，因为每次将链表分成两部分，递归深度为 ( \log n )，而每次合并的时间复杂度是 (O(n))。
• 空间复杂度：由于递归调用的栈空间，空间复杂度为 (O(\log 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) {if(head == null || head.next == null) {return head;}ListNode mid = getMid(head);ListNode left = head;ListNode right = mid.next;mid.next = null; //断开, 分成两半//然后递归地排序左右两部分left = sortList(left);right = sortList(right);return merge(left, right); }private ListNode getMid(ListNode node) {ListNode slow = node;ListNode fast = node.next;while(fast != null && fast.next != null) { //这里是且条件slow = slow.next;fast = fast.next.next; //fast走两步,使用两次next}return slow;}private ListNode merge(ListNode left, ListNode right) {ListNode dummy = new ListNode(0);ListNode current = dummy;while(left != null && right != null) {if(left.val < right.val) {current.next = left;left = left.next;}else {current.next = right;right = right.next;}current = current.next;}if(left != null) {current.next = left;}if(right != null) {current.next = right;}return dummy.next;}
}