2025年- H33-Lc141 --148. 排序链表（快慢指针，快指针先出发一步）--Java版

1.题目描述

2.思路

时间空间复杂度分别为 O(nlogn) 和 O(1)，根据时间复杂度想到二分法，从而联想到归并排序；对数组做归并排序的空间复杂度为 O(n)，分别由新开辟数组 O(n) 和递归函数调用 O(logn) 组成，而根据链表特性：

（1）空节点或者1个节点的情况，直接返回头节点

（2）创建两个快慢指针，快指针比慢指针多走一步

（3）当快指针不等于null，以及快指针的下一节点不为空，快2慢1

    补充：执行完快2慢1，可以确定链表的中点，也就是slow指针的下一个节点，存储变量，平均切分链表。补充：将慢指针的尾部指向null

（4） 左半部分的链表的头节点，右边部分的头节点

（5）创建虚拟头节点，以及指向头节点的指针pre

（6）进行归并排序，左链表和右链表都不为空，实现链表的升序排序

（7）合并链表的时候，如果左右链表不均匀，就把剩余的一个节点直接补齐到链表上

3.代码实现

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }}public class H148 {public ListNode sortList (ListNode head){
//        1.空节点或者1个节点的情况，直接返回头节点if(head==null||head.next==null){return head;}//        2.创建两个快慢指针,快慢指针都从头节点出发，快指针比慢指针多走一步ListNode slow=head;ListNode fast=head.next;//        3.当快指针不等于null，以及快指针的下一节点不为空，快2慢1while(fast!=null&&fast.next!=null) {slow=slow.next;fast=fast.next.next;}//4.可以确定链表的中点，也就是slow指针的下一个节点，存储变量，平均切分链表。ListNode temp=slow.next;//5.切分链表，划分成左右两个部分,将慢指针的尾部指向nullslow.next=null;//6.左半部分的链表的头节点，右边部分的头节点ListNode right=sortList(temp);ListNode left=sortList(head);
//        7.创建虚拟头节点，以及指向头节点的指针preListNode dummyhead=new ListNode(0);ListNode pre=dummyhead;
//        8.进行归并排序，左链表和右链表都不为空，实现链表的升序排序while(right!=null&&left!=null){if(right.val<= left.val){pre.next=right;right=right.next;}else {pre.next=left;left=left.next;}pre=pre.next;//pre指针后移}//        9.合并链表的时候，如果左右链表不均匀，就把剩余的一个节点直接补齐到链表上if(left==null)//左链表遍历完了，右链表还有元素，此时的指针直接指向右链表的剩余元素{pre.next=right;}else {pre.next=left;}return dummyhead.next;}public static void main(String[] args) {H148 test = new H148();ListNode node4 = new ListNode(3, null);ListNode node3 = new ListNode(1, node4);ListNode node2 = new ListNode(2, node3);ListNode head = new ListNode(4, node2);ListNode res = test.sortList(head);System.out.print("输出排序链表的结果；");while (res != null) {System.out.print(res.val);if (res.next != null) {System.out.print("->");}res = res.next;}}}