当前位置：首页 > news >正文

重启人生计划-且随风行

news 来源：原创 2024/9/20 4:50:00

🥳🥳🥳 茫茫人海千千万万，感谢这一刻你看到了我的文章，感谢观赏，大家好呀，我是最爱吃鱼罐头，大家可以叫鱼罐头呦~🥳🥳🥳

如果你觉得这个【重启人生计划】对你也有一定的帮助，加入本专栏，开启新的训练计划，漫长成长路，千锤百炼，终飞升巅峰！无水文，不废话，唯有日以继日，终踏顶峰！ ✨✨欢迎订阅本专栏✨✨

❤️❤️❤️ 最后，希望我的这篇文章能对你的有所帮助！愿自己还有你在未来的日子，保持学习，保持进步，保持热爱，奔赴山海！ ❤️❤️❤️

🔥【重启人生计划】第零章序·大梦初醒🔥

🔥【重启人生计划】第壹章序·明确目标🔥

🔥【重启人生计划】第贰章序·勇敢者先行🔥

🔥【重启人生计划】第叁章序·拒绝内耗🔥

🔥【重启人生计划】第肆章序·积蓄星火🔥

🔥【重启人生计划】第伍章序·浮舟沧海🔥

序言

大家好，我是最爱吃鱼罐头，距离离职已经过去一个月了，目前进度为6，打算重新找工作倒计时24天，当然这其中也会去投递面试。

且行且忘且随风，且行且看且从容。

今日回顾

今天在学习过程中，遇到几个难点，第一，链表花费的时间比较长，因为我做了一些详细的图解，加上自己的理解，从早上一直干到下午才弄完，感觉后续不能这么搞了，除非你们觉得这个图解或者解题思路不错的话，我就会继续做下去。

今天下午的面试题有点难度，像主从同步，binlog啥的，我都得刷一天视频来复习下，才能更好的掌握。明天会看下视频，找下资料去补充下。

回文链表

回文链表📍

回文链表就是以链表中间为中心，两边对称。即 1->2->2->1 ，可以看出从中间隔开两边对称。所以这道题的关键：

找到中间结点，可以以链表的中间结点 📍这道题为例，找出中间结点；
如果是回文链表，那我们可以反转后半部分，即2->1这部分，我们将其反转就变成1->2；
1->2 || 1->2，这样我们可以用后半部分和前半部分进行一一比较，如果有一处不同，就是为false。

代码实现：

package com.ygt.day7;import com.ygt.day4.ListNode;/*** 234. 回文链表* https://leetcode.cn/problems/palindrome-linked-list/description/* 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表.如果是，返回 true ；否则，返回 false 。* 输入：head = [1,2,2,1]* 输出：true* @author ygt* @since 2024/8/17*/
public class IsPalindrome {public static void main(String[] args) {ListNode node5 = new ListNode(1);ListNode node4 = new ListNode(2, node5);ListNode node3 = new ListNode(3, node4);ListNode node2 = new ListNode(2, node3);ListNode node = new ListNode(1, node2);System.out.println(new IsPalindrome().isPalindrome(node));}public boolean isPalindrome(ListNode head) {if(head == null || head.next == null) {return true;}// 1. 找到中间结点// 注意，fast = head.next，为了找到在偶数的中间结点的前一个结点，方便反转。ListNode slow = head, fast = head.next;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}// 2. 反转后半部分ListNode preNode = slow, curNode = slow.next;while (curNode.next != null) {ListNode nextNode = curNode.next;curNode.next = nextNode.next;nextNode.next = preNode.next;preNode.next = nextNode;}// 3. 一一比较ListNode firstNode = head;while ((preNode = preNode.next) != null) {if(firstNode.val != preNode.val) {return false;}firstNode = firstNode.next;}return true;}
}

最后注意虚拟头结点：

链表的一大问题就是操作当前结点必须要找前一个结点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个结点了。

每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。而且很多链表的题目中，都大多数需要用到虚拟头结点。

旋转链表

旋转链表📍

先将给定的链表连接成环，然后将指定位置断开，得到新的起始结点。

注意：

在我们观察案例2的时候，我们可以发现此时的 k = 4，而链表的长度为3，在向右移动到第三步的时候，可以发现，链表变回了原状，第四步的操作也就和第一步的操作一致，那我们是不是可以发现一个规律，我们仅需要向右移动k % n 次就行了即取模运算。因为每次移动n次或者n的倍数次的话，链表就会变为原状，浪费时间，所以我们只需要移动k % n 次即可，而当发现取模后得到结果为0，就直接返回当前结点即可。

特别写下java的取模运算的结果：

System.out.println(4 % 3);   // 1 ==> k = 1
System.out.println(5 % 3);	 // 2 ==> k = 2
System.out.println(6 % 3);	 // 0 ==> k = 0

主要步骤：

首先计算链表的长度，得到链表n的值，并确定好链表的尾结点tailNode；
重新计算k的值，得出是否需要继续进行旋转移动操作；
遍历找到链表最后第k个的结点，即n - k，即旋转的最后一个结点的前一个结点preNode；
将tailNode的next指向首结点head，而preNode的next置空截断，指向null；
最终完成链表的旋转。

图解

我们根据步骤画出一个大概的图解过程：

动图图解

为了更方便查看图解过程，做了个动画：

代码实现：

package com.ygt.day7;import com.ygt.day4.ListNode;/*** 61. 旋转链表* https://leetcode.cn/problems/rotate-list/description/* 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。* 示例 1：* 输入：head = [1,2,3,4,5], k = 2* 输出：[4,5,1,2,3]* @author ygt* @since 2024/8/17*/
public class RotateRight {public static void main(String[] args) {ListNode node5 = new ListNode(5);ListNode node4 = new ListNode(4, node5);ListNode node3 = new ListNode(3, node4);ListNode node2 = new ListNode(2, node3);ListNode node = new ListNode(1, node2);// 打印查看当前效果ListNode.print(node);ListNode listNode = new RotateRight().rotateRight(node, 2);System.out.println();// 打印查看当前效果ListNode.print(listNode);}public ListNode rotateRight(ListNode head, int k) {// 进行校验，如果k = 0或者链表为空，或者链表的next为空，都可以直接返回当前结点if(k == 0 || head == null || head.next == null) {return head;}// 在我们查看案例2的时候，可以发现一个规律，假设链表的长度为n，当向右移动次数k ≥ n时，并且k的值可能会很大，// 所以我们只要移动k % n次即可。而且每次n（或者n的倍数）次移动都是链表的原状态，// 所以推导出新链表的头节点位置为原链表的第n - (k % n)个节点(即从0开始计数)。// 通过第一次遍历得到链表的长度，还有链表的末尾结点int size = 1;ListNode tailNode = head;while(tailNode.next != null) {size++;tailNode = tailNode.next;}// 通过取模计算，重新得到k的值。k = k % size;// 判断是否为n的倍数，是就直接返回即可if(k == 0) {return head;}// 寻找链表最后第k个的结点 preNodeListNode preNode = head;// 由于当前preNode为head结点，多计算了一位，所以需要size - k - 1。for (int i = 0; i < (size - k - 1); i++) {preNode = preNode.next;}// 尾结点闭环tailNode.next = head;// 新的起始结点head = preNode.next;// 截断preNode，置为nullpreNode.next = null;return head;}
}

两两交换链表中的节点

两两交换链表中的节点📍

这道题的思路：

创建虚拟头结点，能更好的移动头结点；
题目要求不修改节点内部的值的情况下完成本题，拒绝你这个偷鸡的想法；
循环遍历，两两交换即可，这道题的思路很简单。

代码实现：

package com.ygt.day7;import com.ygt.day4.ListNode;/*** 24. 两两交换链表中的节点* https://leetcode.cn/problems/swap-nodes-in-pairs/description/* 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。* 输入：head = [1,2,3,4]* 输出：[2,1,4,3]* @author ygt* @since 2024/8/17*/
public class SwapPairs {public static void main(String[] args) {ListNode node5 = new ListNode(5);ListNode node4 = new ListNode(4, node5);ListNode node3 = new ListNode(3, node4);ListNode node2 = new ListNode(2, node3);ListNode node = new ListNode(1, node2);// 打印查看当前效果ListNode.print(node);ListNode listNode = new SwapPairs().swapPairs(node);System.out.println();// 打印查看当前效果ListNode.print(listNode);}public ListNode swapPairs(ListNode head) {if(head == null || head.next == null) {return head;}// 1. 创建虚拟头结点ListNode dummyNode = new ListNode(-1, head);ListNode curNode = dummyNode.next, preNode = dummyNode;// 循环交换while (curNode != null) {// 需要判断是否还有后续结点if(curNode.next != null) {// 交换ListNode nextNode = curNode.next;curNode.next = nextNode.next;nextNode.next = preNode.next;preNode.next = nextNode;}// 最后复位preNode = curNode;curNode = curNode.next;}return dummyNode.next;}
}

合并两个有序链表

合并两个有序链表📍

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

这道题的主要思路：

创建虚拟头结点，作为合并后的新链表头结点的前一个结点；
比较两个链表的每一个结点的大小，小的就添加到新链表的末尾处，直到某一个链表已经遍历结束；
最后补充剩余结点链表到新链表的末尾。

代码实现：

package com.ygt.day7;import com.ygt.day4.ListNode;/*** 21. 合并两个有序链表* https://leetcode.cn/problems/merge-two-sorted-lists/* 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。* 输入：l1 = [1,2,4], l2 = [1,3,4]* 输出：[1,1,2,3,4,4]* @author ygt* @since 2024/8/17*/
public class MergeTwoLists {public static void main(String[] args) {ListNode node = new ListNode(1, new ListNode(2, new ListNode(4)));ListNode node2 = new ListNode(1, new ListNode(3, new ListNode(4)));// 打印查看当前效果ListNode.print(node);ListNode listNode = new MergeTwoLists().mergeTwoLists(node, node2);System.out.println();// 打印查看当前效果ListNode.print(listNode);}public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 判断两个链表是否为空if(list1 == null) {return list2;}if(list2 == null) {return list1;}// 1. 创建虚拟头结点，作为合并后的新链表头结点的前一个结点ListNode dummyNode = new ListNode(-1);ListNode head = dummyNode;// 2. 比较两个链表的每一个结点的大小，小的就添加到新链表的末尾处，直到某一个链表已经遍历结束；while (list1 != null && list2 != null) {if(list1.val <= list2.val) {head.next = list1;list1 = list1.next;}else {head.next = list2;list2 = list2.next;}head = head.next;}// 3. 最后补充剩余结点链表到新链表的末尾。head.next = list1 == null ? list2: list1;return dummyNode.next;}
}

小结算法

今天的算法是有点难度，得多思考下，才能做出来，当然大神的你无需耗费更多的精神就做出来啦。

明日内容

明天刷一下MySQL高级的面试题，如主从以及binlog。

🌸 完结

最后，相关算法的代码也上传到gitee或者github上了。

乘风破浪会有时直挂云帆济沧海

希望从明天开始，一起加油努力吧，成就更好的自己。

🥂 虽然这篇文章完结了，但是我还在，永不完结。我会努力保持写文章。来日方长，何惧车遥马慢！✨✨✨

💟 感谢各位看到这里！愿你韶华不负，青春无悔！让我们一起加油吧！ 🌼🌼🌼

💖 学到这里，今天的世界打烊了，晚安！🌙🌙🌙