网站你懂我意思正能量晚上在线观看不用下载免费,南京模板建站定制网站,带分销的小程序,海南在线人才网招聘官网废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【链表的排序】#xff0c;使用【链表】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【链表的排序】使用【链表】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。 以及重排链表
附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
链表排序【MID】
单链表的升序排列
题干 解题思路
而链表中我们也可以用【合并K个有序链表】同样的方式当链表被划分到只剩一个节点时就一定有序。只需要找到中间个元素的前一个节点将其断开就可以将链表分成两个子链表然后继续划分直到最小然后往上依次合并。
终止条件 当子链表划分到为空或者只剩一个节点时不再继续划分往上合并。返回值 每次返回两个排好序且合并好的子链表。本级任务 找到这个链表的中间节点从前面断开分为左右两个子链表进入子问题排序。
怎么找中间元素呢我们可以使用快慢双指针快指针每次两步慢指针每次一步那么快指针到达链表尾的时候慢指针正好走了快指针距离的一半为中间元素。
具体做法
step 1【入参判断】首先判断链表为空或者只有一个元素直接就是有序的。step 2【找中间节点】准备三个指针快指针right每次走两步慢指针mid每次走一步前序指针left每次跟在mid前一个位置。三个指针遍历链表当快指针到达链表尾部的时候慢指针mid刚好走了链表的一半正好是中间位置。step 3【划分子问题】从left位置将链表断开刚好分成两个子问题开始递归。step 4【合并子问题】将子问题得到的链表合并参考合并两个有序链表。
代码实现
给出代码实现基本档案 基本数据结构链表 辅助数据结构无 算法分治 技巧双指针快慢指针 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;/** public class ListNode {* int val;* ListNode next null;* public ListNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param head ListNode类 the head node* return ListNode类*/public ListNode sortInList (ListNode head) {// 1 入参判断如果链表只剩一个节点或者空则直接有序到达终止条件if (head null || head.next null) {return head;}// 2 中间位置为慢指针的下一个节点奇数节点链表为正中间偶数则为另一半的开头所以后半段一定是mid.nextListNode mid findMidNode(head);// 3 设置后半段链表断开前后半段链表ListNode newHead mid.next;mid.next null;// 4 合并两段有序链表return mergeSortList(sortInList(head), sortInList(newHead));}// 寻找链表中间节点private ListNode findMidNode(ListNode head) {ListNode fast head;ListNode slow head;while (fast.next ! null fast.next.next ! null) {fast fast.next.next;slow slow.next;}// 3 中间位置为慢指针的下一个节点奇数节点链表为正中间偶数则为另一半的开头return slow;}// 合并两个有序链表private ListNode mergeSortList(ListNode pHead1, ListNode pHead2) {// 1 入参判断if (pHead1 null pHead2 null) {return null;}if (pHead1 null) {return pHead2;}if (pHead2 null) {return pHead1;}// 2 设置结果链表ListNode dummy new ListNode(-1);ListNode p dummy;while (pHead1 ! null pHead2 ! null) {if (pHead1.val pHead2.val) {p.next pHead1;pHead1 pHead1.next;} else {p.next pHead2;pHead2 pHead2.next;}p p.next;}// 3 如果其中一个链表为空后续直接接另一个if (pHead1 null) {p.next pHead2;}if (pHead2 null) {p.next pHead1;}return dummy.next;}
}复杂度分析 链表的奇偶重排【MID】
需要注意的是节点的位置而非节点的值
题干 解题思路
核心思路就是奇数位节点和偶数位节点断掉重连
step 1判断空链表的情况如果链表为空不用重排。如果链表只有一个节点也不用重排step 2使用双指针odd和even分别遍历奇数节点和偶数节点并给偶数节点链表一个头。step 3上述过程每次遍历两个节点且even在后面因此每轮循环用even检查后两个元素是否为NULL如果不为再进入循环行上述连接过程。step 4将偶数节点头接在奇数最后一个节点后再返回头部。
代码实现
给出代码实现基本档案 基本数据结构链表 辅助数据结构无 算法迭代 技巧双指针同向指针 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;/** public class ListNode {* int val;* ListNode next null;* public ListNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param head ListNode类* return ListNode类*/public ListNode oddEvenList (ListNode head) {// 1 入参条件判断if (head null) {return null;}if (head.next null) {// 只有1个节点不用重排return head;}// 2 设置偶数虚拟头节点,并设定奇偶双指针ListNode odd head;ListNode evenDummy head.next;ListNode even evenDummy;// 3 遍历链表往奇数和偶数节点上补充对应节点,因为even在后边所以要以even做判断否则对于1-2-3-4这种情况//odd结束时指向nullnull.next会有问题返回仍然是nullwhile (even ! null even.next ! null) {// 奇数位断开指向偶数的指针并指向下一个奇数位odd.next even.next;odd odd.next;// 偶数位断开指向奇数的指针并指向下一个偶数位even.next odd.next;even even.next;}// 4 遍历完后偶数整体接到奇数后odd.next evenDummy;return head;}
}复杂度分析
时间复杂度O(n)遍历一次链表的所有节点 空间复杂度O(1)常数级指针无额外辅助空间
重排链表【MID】
复杂度升级了一些不过套路类似
题干 解题思路
注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。这样我们的任务即可划分为三步
【找到中点】找到原链表的中点参考「876. 链表的中间结点」。我们可以使用快慢指针来 O(N)O(N)O(N) 地找到链表的中间节点。【反转右半边】将原链表的右半端反转参考「206. 反转链表」。我们可以使用迭代法实现链表的反转。【合并两个链表】将原链表的两端合并。因为两链表长度相差不超过 11因此直接合并即可。
以上需要注意的是找链表中点时对于奇数个节点中点为前半段链表所有从题目示例可以看出
代码实现
给出代码实现基本档案 基本数据结构链表 辅助数据结构无 算法迭代 技巧双指针 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
/*** 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 void reorderList(ListNode head) {// 1 入参校验if (head null || head.next null) {return ;}// 2 找到链表中点断开后半段链表这次要找的mid要偏右一些前半段保留偏长这样后续交替衔接才没问题ListNode mid middleNode(head);ListNode l1 head;ListNode l2 mid.next;mid.next null;// 3 反转后半段链表l2 reverse(l2);// 4 将反转后链表连接到原链表中mergeList(l1, l2);}// 交替合并两个链表private void mergeList(ListNode l1, ListNode l2) {ListNode pNext1;ListNode pNext2;// 因为两个链表仅仅相差1所以直接交替合并即可while (l1 ! null l2 ! null) {// 暂存两个链表的下一个节点pNext1 l1.next;pNext2 l2.next;// 交替衔接l1和l2l1.next l2;l1 pNext1;l2.next l1;l2 pNext2;}}// 寻找中间节点private ListNode middleNode(ListNode head) {ListNode slow head;ListNode fast head;while (fast.next ! null fast.next.next ! null) {slow slow.next;fast fast.next.next;}return slow;}// 反转链表private ListNode reverse(ListNode head) {ListNode pre null;ListNode cur head;while (cur ! null) {ListNode pNext cur.next;cur.next pre;pre cur;cur pNext;}return pre;}
}复杂度分析
时间复杂度遍历了链表时间复杂度为ON 空间复杂度没有使用额外空间空间复杂度为O1
