Java数据结构链表分割和链表排序使用极快排序、归并排序、集合排序、迭代、递归，刷题的重点

148. 排序链表 - 力扣（LeetCode）

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

上一道题并没有让合并之后还要进行排序，本题不仅要分隔之后还要进行排序，此时可以想到很多种方法，比如堆排序，快速排序，归并排序等等。看似简单，却是很多大厂的面试题。

题目的进阶问题要求达到 O(nlogn) 的时间复杂度和 O(1) 的空间复杂度

时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O（n^2），其中最适合链表的排序算法是归并排序。

学新通

2.1先介绍一个最容易最简单的方法

都存到集合中，排序后再进行赋值，如果写出这样，面试可能要回家喽！！！

class Solution {
//思路，先把链表存到数组，排序后重新更新链表
public ListNode sortList(ListNode head) {
ArrayList<Integer> list = new ArrayList();
ListNode p = head;
while(p != null){
list.add(p.val);
p = p.next;
}
Collections.sort(list);
p = head;
for(int i = 0;i<list.size();i ){
p.val = list.get(i);
p = p.next;
}
return head;
}
}

2.2普通归并排序（自顶向下）

使用快慢指针进行找到中间节点，然后进行归并排序

public ListNode sortList(ListNode head){
return mergeSort(head);
}
// 找到一个链表的中点
public ListNode findMid(ListNode head) {
if (head == null) return head;
ListNode fast = head.next; // 快指针每次走2步
ListNode slow = head; // 慢指针每次走1步
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public ListNode mergeSort(ListNode head) {
// 当head.next==null时说明当前链表只有一个元素无序再排序
if (head == null || head.next == null) {
return head;
}
// 找到中间节点
ListNode mid = findMid(head);
// 存储中间节点的下一个结点
ListNode next = mid.next;
// 从中间结点断开分别对两边进行mergeSort
mid.next = null;
// 返回排序后的头节点
ListNode left = mergeSort(head);
ListNode right = mergeSort(next);
// 返回合并之后的头节点
return merge(left, right);
}
public ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode curr = dummy;
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;
}
if (l1 != null) {
curr.next = l1;
}
if (l2 != null) {
curr.next = l2;
}
return dummy.next;
}

2.3借鉴大佬的归并排序（自底向上也是最难的，空间复杂度o(1)）

class Solution {
public ListNode sortList(ListNode head) {
ListNode dummy = new ListNode(-1, head);
// 获取链表的长度
int len = 0;
ListNode curr = head;
while (curr!=null) {
len ;
curr = curr.next;
}
// 循环遍历
// 外层遍历step 内层处理每step个元素进行一次merge
for (int step=1; step<len; step*=2) {
ListNode tail = dummy;
curr = dummy.next;
while (curr!=null) {
ListNode left = curr;
ListNode right = cut(left, step);
curr = cut(right, step);
tail.next = merge(left, right);
while (tail.next!=null) {
tail = tail.next;
}
}
}
return dummy.next;
}
// 将链表从from开始切掉前step个元素，返回后一个元素
public ListNode cut(ListNode from, int step) {
step--;
while (from!=null && step>0) {
from = from.next;
step--;
}
if (from==null) {
return null;
} else {
ListNode next = from.next;
from.next = null;
return next;
}
}
// 将两个有序链表合并成一个，返回合并后的头节点
public ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode curr = dummy;
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;
}
if (l1!=null) {
curr.next = l1;
}
if (l2!=null) {
curr.next = l2;
}
return dummy.next;
}
}

2.4面试官让你用快排实现，不会做也得会

public ListNode sortList3(ListNode head) {
return quickSortLinkedList(head)[0];
}
public ListNode[] quickSortLinkedList(ListNode head) {
if(head == null || head.next == null) return new ListNode[]{head,head};
//pivot为head，定义跟踪分割左右两个链表的头尾指针
ListNode p = head.next,headSmall= new ListNode(),
headBig = new ListNode(),tailSmall = headSmall, tailBig = headBig;
//partition操作，以pivot为枢纽分割为两个链表
while(p != null){
if(p.val < head.val){
tailSmall.next = p;
tailSmall = tailSmall.next;
}else{
tailBig.next = p;
tailBig = tailBig.next;
}
p = p.next;
}
//断开<pivot的排序链表、pivot、>=pivot的排序链表，链表变为三个部分
head.next = null;
tailSmall.next = null;
tailBig.next = null;
//递归partition
ListNode[] left = quickSortLinkedList(headSmall.next);
ListNode[] right = quickSortLinkedList(headBig.next);
//如果有<pivot的排序链表、连接pivot
if(left[1] != null) {
left[1].next = head;
}
//连接pivot、>=pivot的排序链表
head.next = right[0];
//确定排序后的头节点和尾节点
ListNode newHead,newTail;
if(left[0] != null) newHead = left[0];
else newHead = head;
if(right[1] != null) newTail = right[1];
else newTail = head;
//返回当前层递归排序好的链表头节点和尾节点
return new ListNode[]{newHead,newTail};
}

2.5快排2：

用6个指针，分别指向小于部分的头h1和尾t1、等于部分的头h2和尾t2、大于部分的头h3和尾t3。

class Solution {
public ListNode sortList(ListNode head) {
return quickSort(head);
}
public ListNode quickSort(ListNode head) {
if (head==null || head.next==null) {
return head;
}
ListNode h1 = new ListNode();
ListNode h2 = new ListNode();
ListNode h3 = new ListNode();
ListNode t1 = h1;
ListNode t2 = h2;
ListNode t3 = h3;
ListNode curr = head;
int pivot = getMid(head).val; // 用中间节点的原因是，如果每次用最左边的结点，对于纯递增和纯递减的case就退化为O(n)
while (curr!=null) {
ListNode next = curr.next;
if (curr.val < pivot) {
curr.next = null;
t1.next = curr;
t1 = t1.next;
} else if (curr.val == pivot) {
curr.next = null;
t2.next = curr;
t2 = t2.next;
} else {
curr.next = null;
t3.next = curr;
t3 = t3.next;
}
curr = next;
}
// < 的链表和 > 的链表分别快排
h1 = quickSort(h1.next);
h3 = quickSort(h3.next);
// h1链表不一定有元素 h2链表一定有元素先把h2、h3连起来
h2 = h2.next;
t2.next = h3;
// 如果h1链表为空直接返回h2即可
// 否则找到h1链表的结尾，连上h2的头
if (h1==null) {
return h2;
} else {
t1 = h1;
// 找到t1链表的结尾
while (t1.next!=null) {
t1 = t1.next;
}
t1.next = h2;
return h1;
}
}
public ListNode getMid(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast!=null && fast.next!=null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}

merge 函数里只有一个 dummy 指针是新建的，后续节点都是直接拼接原链表的数据，所以一次 merge 操作的空间复杂度是 O(1)。而且 CPU 一次只能执行一个 merge 函数，merge 函数执行一次后，栈上申请的空间都释放掉了，所以，没有递归的解法，总的空间复杂度还是 O(1)。

这篇好文章是转载于：学新通技术网

Java数据结构链表分割和链表排序使用极快排序、归并排序、集合排序、迭代、递归，刷题的重点

本篇主要介绍在单链表进行分割，单链表进行分隔并使用快速排序、归并排序、集合排序、迭代、递归等方法的总结，愿各位大佬喜欢~~

一、分隔链表

二、排序链表

2.1先介绍一个最容易最简单的方法

2.2普通归并排序（自顶向下）

2.3借鉴大佬的归并排序（自底向上也是最难的，空间复杂度o(1)）

2.4面试官让你用快排实现，不会做也得会

2.5快排2：

photoshop保存的图片太大微信发不了怎么办

Android 11 保存文件到外部存储，并分享文件

word里面弄一个表格后上面的标题会跑到下面怎么办

《学习通》视频自动暂停处理方法

微信公众号没有声音提示怎么办

photoshop扩展功能面板显示灰色怎么办

怎样阻止微信小程序自动打开

excel下划线不显示怎么办

excel打印预览压线压字怎么办

photoshop蒙版画笔没反应怎么办