湛江网站建设的详细过程,免费的网站推广方法,做非法网站要多少钱,wordpress插件audio player链表高频题目和必备技巧
1. 链表类题目注意点
1#xff0c;如果笔试中空间要求不严格#xff0c;直接使用容器来解决链表问题
2#xff0c;如果笔试中空间要求严格、或者在面试中面试官强调空间的优化#xff0c;需要使用额外空间复杂度**O(1)**的方法
3#xff0c;最…链表高频题目和必备技巧
1. 链表类题目注意点
1如果笔试中空间要求不严格直接使用容器来解决链表问题
2如果笔试中空间要求严格、或者在面试中面试官强调空间的优化需要使用额外空间复杂度**O(1)**的方法
3最常用的技巧-快慢指针
4链表类题目往往都是很简单的算法问题核心考察点也并不是算法设计是coding能力
5这一类问题除了多写多练没有别的应对方法
注意: 链表类问题既然练的就是coding那么不要采取空间上讨巧的方式来练习
注意: 链表相关的比较难的问题是约瑟夫环问题会在之后补充
2. 相关题目
注意
这些题目往往难度标为“简单”是因为用容器解决真的很简单
但是不用容器、实现额外空间复杂度O(1)的方法并不轻松包括很多提交的答案也都没有符合要求 题目1 : 返回两个无环链表相交的第一个节点 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/ 思路 先判断是否不相交 若有一个为空则不相交长链表提前走差值个, 随后两链表一同走, 走到尾巴, 若不相同, 则不相交 两链表从头走, 直至寻找到第一个公共节点 代码 public static ListNode getIntersectionNode(ListNode h1, ListNode h2) {// 1. 先判断是否不相交// 边界: 只要有一个为空就不相交if (h1 null || h2 null) {return null;}ListNode a h1, b h2;// 计算两个链表长度之差int diff 0;while (a.next ! null) {a a.next;diff;}// a来到最后一个结点while (b.next ! null) {b b.next;diff--;}// b来到最后一个结点// 边界: 如果两个链表的尾结点不相等, 则一定不相交if (a ! b) {return null;}// 2. 寻找第一个公共结点// 如果长度不等,把长链表给a,短链表给bif (diff 0) {a h1;b h2;} else {a h2;b h1;}// 取差值的绝对值diff Math.abs(diff);// 长链表先走差值步while (diff-- ! 0) {a a.next;}// 长链表和短链表一起走while (a ! b) {a a.next;b b.next;}// 当再次相交的时候停止return a;}题目2 : 每k个节点一组翻转链表 测试链接https://leetcode.cn/problems/reverse-nodes-in-k-group/ 思路 由于要返回总的头结点, 单独讨论第一组 第一组够不够k个, 不够直接返回head第一组反转(反转的过程中, lastTeamEnd.next指向下一组的头), 并记录反转后的头,用于返回反转后记录lastTeamEnd为原来的head(start), 讨论接下来其他组 判断接下来的组够不够k个, 不够直接返回 够了,翻转,调整将上一组的尾连到这一组的头, lastTeamEnd来到这一组的尾 一致循环到没有下一组 代码 public static ListNode reverseKGroup(ListNode head, int k) {// 1. 先讨论第一组ListNode start head;// 看第一组够不够k个ListNode end teamEnd(start, k);if (end null) {return head;}// 第一组 很特殊因为牵扯到换头的问题head end;// 反转后头变成尾reverse(start, end);// 在反转的过程中会连上下一组// 翻转之后start变成了上一组的结尾节点ListNode lastTeamEnd start;// 前一组的头变成了尾// 2. 接下来的其他组while (lastTeamEnd.next ! null) {// 下一组还有没有start lastTeamEnd.next;// 下一组的初头end teamEnd(start, k);// 下一组的初尾if (end null) {// 不够return head;// 直到下一组不够k个}reverse(start, end);// 够了,反转lastTeamEnd.next end;// 上一组的尾巴要连到这一组的end(反转后变成头)lastTeamEnd start;// 该组变为要调整的下一组的上一组}return head;// 直到没有下一组}// 当前组的开始节点是s往下数k个找到当前组的结束节点返回public static ListNode teamEnd(ListNode s, int k) {while (--k ! 0 s ! null) {// 当前计数s s.next;// 走向下一个}return s;}// s - a - b - c - e - 下一组的开始节点// 上面的链表通过如下的reverse方法调整成 : e - c - b - a - s - 下一组的开始节点public static void reverse(ListNode s, ListNode e) {e e.next;// 先保存下一组的第一个节点ListNode pre null, cur s, next null;while (cur ! e) {// 当前节点不是下一组的结点, 反转next cur.next;cur.next pre;pre cur;cur next;}s.next e;// 将下一组的结点连在反转后的尾巴上}题目3 : 复制带随机指针的链表 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/ 思路 将原来的结点每一个都赋值一份放在原节点的后面, 将原节点和现节点串在一起利用新老节点的关系, 设置每一个新节点的random指针老链表分离 : 老链表重新连在一起新链表重新连在一起返回新链表的头节点 代码 public static Node copyRandomList(Node head) {// 特殊处理if (head null) {return null;}// 克隆// 1 - 2 - 3 - ...// 变成 : 1 - 1 - 2 - 2 - 3 - 3 - ...Node cur head;Node next null;while (cur ! null) {next cur.next;// 记录下一个cur.next new Node(cur.val);// 克隆cur.next.next next;// 原来的下一个接在克隆后的节点上cur next;// 当前节点走到原来的下一个}// 利用上面新老节点的结构关系设置每一个新节点的random指针cur head;Node copy null;while (cur ! null) {next cur.next.next;// 记录下一个值copy cur.next;// 记录当前节点的克隆节点copy.random cur.random ! null ? cur.random.next : null;cur next;}// 新老链表分离 : 老链表重新连在一起新链表重新连在一起Node ans head.next;// 记录新链表的头节点cur head;while (cur ! null) {next cur.next.next;copy cur.next;cur.next next;// 原链表恢复原状copy.next next ! null ? next.next : null;cur next;}// 返回新链表的头节点return ans;}题目4 : 判断链表是否是回文结构。这个题的流程设计甚至是考研常用。快慢指针找中点。 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/ 思路 利用快慢指针找中点 找到后中点就是slow从中点开始往后的节点逆序 开始头尾对照,设置临时变量进行处理,以保留原来的结点用于还原链表 把链表调整回原来的样子再返回判断结果 代码 public static boolean isPalindrome(ListNode head) {// 特例判断if (head null || head.next null) {// 没有/只有一个结点return true;}// 1. 快慢指针找中点ListNode slow head, fast head;while (fast.next ! null fast.next.next ! null) {slow slow.next;fast fast.next.next;}// fast跳不了// 2. 现在中点就是slow从中点开始往后的节点逆序// head - ... - slow - ... - ...ListNode pre slow;ListNode cur pre.next;ListNode next null;pre.next null;// ! 原来slow.next要先保留,赋值给cur, 随后中点的next要悬空(用于后续翻转时作为判断值)while (cur ! null) {next cur.next;// 以防cur-next改变后后续指针丢失cur.next pre;pre cur;cur next;}// 3. 开始对照,设置临时变量进行处理,以保留原来的结点用于还原链表boolean ans true;ListNode left head;ListNode right pre;// head - ... - slow - ... - pre// left往右、right往左每一步比对值是否一样如果某一步不一样答案就是falsewhile (left ! null right ! null) {// 循环至中点的next null,说明为回文结构if (left.val ! right.val) {ans false;break;// 先不返回, 把链表复原}left left.next;right right.next;}// 4. 把链表调整回原来的样子再返回判断结果// head - ... - slow - ... - pre// pre - ... - slowcur pre.next;pre.next null;next null;while (cur ! null) {// 中点的next为nullnext cur.next;cur.next pre;pre cur;cur next;}return ans;}某考研题要求收尾挨个相接也用的同样的方法 题目5 : 返回链表的第一个入环节点。快慢指针找中点。 测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/ 思路 特殊处理设置双指针, 若f在跳的过程中先走到null, 说明无环, 返回当fs相遇, f回到头结点, s不变f每次跳一步, s每次跳一步最后相遇时, 一定是在入环的第一个节点 代码 public static ListNode detectCycle(ListNode head) {// 特殊处理: 为null, 只有一个结点, 只有两个结点且能到头if (head null || head.next null || head.next.next null) {return null;}// 1. f跳两步 s跳一步ListNode slow head.next;// 已经排除过特殊情况,直接往下跳ListNode fast head.next.next;while (slow ! fast) {// !!如果f先走到头, 说明没有环if (fast.next null || fast.next.next null) {return null;}slow slow.next;fast fast.next.next;}// 2. 相遇时, f回到头结点, s保持不变fast head;// 3. f跳一步 s跳一步while (slow ! fast) {slow slow.next;fast fast.next;}// 4. 最后相遇时一定是在入环的第一个节点return slow;}题目6 : 在链表上排序。要求时间复杂度O(n * log n)额外空间复杂度O(1)还要求排序有稳定性。 测试链接 : https://leetcode.cn/problems/sort-list/ 思路 计算链表的长度, 用于限制步长开始按照步长进行排序 先处理第一组,因为排序后很可能要换头继续处理其他组 代码 public static ListNode sortList(ListNode head) {// 计算链表的长度, 用于限制步长int n 0;ListNode cur head;while (cur ! null) {n;cur cur.next;}// l1...r1 每组的左部分// l2...r2 每组的右部分// next 下一组的开头// lastTeamEnd 上一组的结尾ListNode l1, r1, l2, r2, next, lastTeamEnd;for (int step 1; step n; step 1) {// 进来了,说明stepn,即n2// 第一组很特殊因为要决定整个链表的头所以单独处理// 找第一组的头尾, 第二组的头尾, 保存剩余链表的头部并将12组分离l1 head;r1 findEnd(l1, step);l2 r1.next;r2 findEnd(l2, step);next r2.next;r1.next null;r2.next null;merge(l1, r1, l2, r2);head start;// 临时保存lastTeamEnd end;// 接下来的其他组while (next ! null) {l1 next;r1 findEnd(l1, step);l2 r1.next;if (l2 null) {// 若l2不存在, 则无需进行合并, 直接停止lastTeamEnd.next l1;// 尾接头,break不是return,因为要继续外层的循环break;}r2 findEnd(l2, step);next r2.next;r1.next null;// !!!!都是断开r!!!!!!!!!!!!!r2.next null;merge(l1, r1, l2, r2);lastTeamEnd.next start;// 将上一组和调整好的这一组链接在一起lastTeamEnd end;// 这一组的尾变成lastTeamEnd}}return head;}// 包括s在内往下数k个节点返回// 如果不够返回最后一个数到的非空节点public static ListNode findEnd(ListNode s, int k) {while (s.next ! null --k ! 0) {s s.next;}return s;}public static ListNode start;public static ListNode end;// l1...r1 - null : 有序的左部分// l2...r2 - null : 有序的右部分// 整体merge在一起保证有序// 并且把全局变量start设置为整体的头全局变量end设置为整体的尾public static void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) {ListNode pre;// 找头if (l1.val l2.val) {start l1;pre l1;l1 l1.next;} else {start l2;pre l2;l2 l2.next;}// 合并while (l1 ! null l2 ! null) {if (l1.val l2.val) {pre.next l1;pre l1;l1 l1.next;} else {pre.next l2;pre l2;l2 l2.next;}}// 找尾if (l1 ! null) {pre.next l1;end r1;} else {pre.next l2;end r2;}}
