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

news/2024/10/31 3:31:28/

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

86. 分隔链表 - 力扣（LeetCode）

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

目录

一、分隔链表

二、排序链表

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

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

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

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

2.5快排2：

一、分隔链表

86. 分隔链表 - 力扣（LeetCode）

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

在分隔链表时，先考虑如何去分隔链表，怎么保证节点的next不形成环。

方法一：也是笨方法，找到第一个>x的值将小的值都逐个进行头插，随后将next指向第一个>x的值

class Solution {public ListNode partition(ListNode head, int x) {if (head == null || head.next == null) {return head;}ListNode mark = new ListNode(0, head);ListNode cur1 = mark;while (cur1.next != null && cur1.next.val < x) {cur1 = cur1.next;}ListNode firstMaxOrNull = cur1.next;ListNode cur2 = cur1;while (cur2 != null && cur2.next != null) {if (cur2.next.val >= x) {cur2 = cur2.next; } else {cur1.next = cur2.next;cur2.next = cur2.next.next;cur1 = cur1.next;cur1.next = null;}}cur1.next = firstMaxOrNull;return mark.next;}
}

方法二：创建俩个链表进行分别插入，最后合并俩个链表

public ListNode partition(ListNode head, int x) {ListNode minLink = new ListNode(0);//记录小值链表的头ListNode minP = minLink;//对小表操作用的指针ListNode maxLink = new ListNode(0);//记录大值链表的头ListNode maxP = maxLink;//同理while(head!=null){if(head.val < x){//找到小的值minP.next = head;//放入minLink中，操作指针后移一位minP = head;}else{maxP.next = head;//放入maxLink中，操作指针后移一位maxP = head;}head = head.next;}//遍历完成后记得后一段链表的最后节点指向null;maxP.next = null;//两段拼接minP.next = maxLink.next;return minLink.next;}

二、排序链表

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;// 从中间结点断开 分别对两边进行mergeSortmid.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个元素进行一次mergefor (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;//递归partitionListNode[] left = quickSortLinkedList(headSmall.next);ListNode[] right = quickSortLinkedList(headBig.next);//如果有<pivot的排序链表、连接pivotif(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)。 


http://www.ppmy.cn/news/26850.html

相关文章

C++调用Python脚本进行18次循环操作后，脚本不执行

C++调用Python脚本进行18次循环操作后，脚本不执行

C调用Python脚本进行18次循环操作后&#xff0c;脚本不执行 现象&#xff1a; 发送端接收端 从第二张图中可以看出&#xff0c;python脚本卡在’[parkin_debug] 6’与’[parkin_debug] 7’之间 该测试经过多次反复测试&#xff0c;均在第18次循环执行时&#xff0c;出现上述问…
阅读更多...
【Git】为什么需要版本控制？版本控制工具有那些？

【Git】为什么需要版本控制？版本控制工具有那些？

目录 一、为什么需要版本控制&#xff1f; 二、版本控制工具有那些&#xff1f; &#x1f49f; 创作不易&#xff0c;不妨点赞&#x1f49a;评论❤️收藏&#x1f499;一下 一、为什么需要版本控制&#xff1f; 首先我们要知道什么是版本控制&#xff1f;对版本控制进行文字…
阅读更多...
Java环境变量配置

Java环境变量配置

一、Path环境变量配置设置环境变量的值&#xff1a;C:\Program Files\Java\jdk-17\bin目前较新的JDK安装时会自动配置javac、java程序的路径到Path环境变量中去 &#xff0c;因此&#xff0c;javac、java可以直接使用。注意&#xff1a;以前的老版本的JDK在安装的是没有自动配置…
阅读更多...
resp连接redis服务器

resp连接redis服务器

修改redis的配置文件使得windows的图形界面客户端可以连接redis服务器 resp安装好以后&#xff0c;可以在linux端打开redis.conf中做以下操作&#xff0c;使得windows的图形界面客户端可以连接redis服务器 方法一&#xff1a; 1&#xff0c;在redis.conf文件中添加bind 在文件…
阅读更多...
Rust编程细节知识点拾遗

Rust编程细节知识点拾遗

1.Rust中每一个引用都有生命周期&#xff0c;也就是引用保持有效的作用域。生命周期主要目标是避免悬垂引用&#xff0c;悬垂引用就是引用了已经释放的值。函数中&#xff0c;x的生命周期不能小于返回值得生命周期。当有x和y的时候&#xff0c;两者的生命周期是两个里面较小的那…
阅读更多...
QHash-官翻

QHash-官翻

QHash 类 template <typename Key, typename T> class QHash QHash 类是一种模板类&#xff0c;提供基于哈希表的字典类结构。更多内容… 头文件:#include <QHash>qmake:QT core派生类:QMultiHash 所有成员列表&#xff0c;包括继承的成员废弃的成员 注意&…
阅读更多...
微服务之Eureka

微服务之Eureka

&#x1f3e0;个人主页&#xff1a;阿杰的博客 &#x1f4aa;个人简介&#xff1a;大家好&#xff0c;我是阿杰&#xff0c;一个正在努力让自己变得更好的男人&#x1f468; 目前状况&#x1f389;&#xff1a;24届毕业生&#xff0c;奋斗在找实习的路上&#x1f31f; &#x1…
阅读更多...
唤醒手腕 Java 后端 Springboot 结合 Redis 数据库学习笔记（更新中）

唤醒手腕 Java 后端 Springboot 结合 Redis 数据库学习笔记（更新中）

Redis 基本介绍 Redis Introduction The open source, in-memory data store used by millions of developers as a database, cache, streaming engine, and message broker. 基本概念&#xff1a;redis 是一个开源的、使用 C 语言编写的、支持网络交互的、可基于内存也可持…
阅读更多...
最新文章

Copyright @ 2022~2023