Leetcode 排序链表
这段代码的算法思想是 归并排序，一种适合链表的排序方法。它通过递归地将链表拆分成两部分，分别排序，然后合并已排序的部分，从而达到整体排序的目的。以下是代码的中文解释：
算法步骤：
-
找到链表的中点：
- 在
getMid方法中，使用了快慢指针（slow和fast指针）来找到链表的中间节点。 fast指针每次移动两步，slow指针每次移动一步。当fast指针到达链表末尾时，slow指针刚好位于链表中间。- 将链表分为左右两部分，
slow为中间节点，从而将链表一分为二。
- 在
-
递归地排序两部分链表：
sortList方法中，通过递归地对左半部分和右半部分链表进行排序。递归的终止条件是链表为空或只有一个节点，这时链表已是有序的。- 对左右两部分链表分别调用
sortList方法，进行递归排序，最终会得到两个已排序的子链表。
-
合并两个有序链表：
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;}
}