上海市建设部注册中心网站,网站开发的收获体会,开发网站多少钱一个月,石景山保安公司#x1f525;博客主页#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞#x1f44d;收藏⭐评论✍ 文章目录 1.0 链表的创建 2.0 判断回文链表说明 2.1 快慢指针方法 2.2 使用递归方式实现反转链表方法 2.3 实现判断回文链表 - 使用快慢指针与反转链表方法 3.0 判断环链表说明… 博客主页 【小扳_-CSDN博客】 ❤感谢大家点赞收藏⭐评论✍ 文章目录 1.0 链表的创建 2.0 判断回文链表说明 2.1 快慢指针方法 2.2 使用递归方式实现反转链表方法 2.3 实现判断回文链表 - 使用快慢指针与反转链表方法 3.0 判断环链表说明 3.1 实现判断环链表与寻找环入口节点 - 龟兔赛跑算法实现 3.2 解释为什么第一次相遇后兔、龟每一次都走一步最终会相遇且该节点是环入口节点的原因 4.0 实现判断回文链表、判断环链表且寻找环入口节点的完整代码 1.0 链表的创建 链表是一种常见的数据结构用于存储一系列元素。链表由节点组成每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以分为单向链表和双向链表其中单向链表的节点只有一个指针指向下一个节点而双向链表的节点有两个指针分别指向前一个节点和后一个节点。 为后续实现算法方便这里需要实现一个带哨兵节点的单链表。
代码如下 import java.util.Iterator;public class List implements IterableInteger{private final Node sentry;static class Node {public int value;public Node next;public Node() {}public Node(int value, Node next) {this.value value;this.next next;}Overridepublic String toString() {return Node{ value value };}}//外部类构造器初始化哨兵节点public List() {sentry new Node(-1,null);}//头插节点public void addFirst(int value) {this.sentry.next new Node(value,this.sentry.next);}//尾插节点public void addLats(int value) {Node p this.sentry;while (p.next ! null) {p p.next;}p.next new Node(value,null);}//重写迭代器Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p sentry.next;Overridepublic boolean hasNext() {return p ! null;}Overridepublic Integer next() {int k p.value;p p.next;return k;}};}}简单对以上代码进行分析将链表进行封装成一个外部类静态内部类则是节点类进行封装。外部类的成员变量为一个哨兵节点内部类的成员变量为 int value 值、 Node next 指向下一个节点的引用变量。外部类实现了头插节点、尾插节点、重写了迭代器等。 需要了解可以点击该链接Java 数据结构篇-实现单链表核心API-CSDN博客 2.0 判断回文链表说明 回文链表是指一个链表从头到尾和从尾到头读是一样的也就是说链表的节点值按照顺序排列和逆序排列是相同的。例如链表 1 - 2 - 3 - 2 - 1 就是一个回文链表因为从头到尾读和从尾到头读都是 1 - 2 - 3 - 2 - 1。 2.1 快慢指针方法 实现判断回文链表时需要用到快慢指针方法来寻找中间节点。 具体思路实现快慢指针找中间节点定义两个指针对于 fast 指针来说每一次循环都要走两步直到 fast null 或者 fast.next null遇到这两种情况都要结束循环了注意不要缺少了 fast.next null 的情况不然有可能抛出 空指针异常 对于 slow 指针来说每一次循环都要走一步直到退出循环后若链表的节点的数量为奇数时则指向的节点就是中间节点。 若链表的节点的数量为偶数时则指向的节点是中间两个节点的后一个节点。例如链表 1 - 2 - 3 - 3 - 2 - 1 - null此时循环结束后slow 指针指向的是靠后面值为 3 的节点。
代码如下 //查找链表中的中间的节点(快慢指针):假如为奇数则需要找到中间的节点// 假如是偶数则需要找到中间的两个节点的后一个节点。public Node searchMidNode() {//判断是否为空链表if (this.sentry.next null) {return null;}Node fast this.sentry.next;Node slow this.sentry.next;while (fast! null fast.next ! null) {fast fast.next.next;slow slow.next;}return slow;} 2.2 使用递归方式实现反转链表方法 实现判断回文链表时需要实现反转链表。 具体思路先考虑递出的终止条件为当 p.next null 时则返回 p 这个节点。再考虑在回归的过程中需要将该 p 节点一直回归到回归过程结束为止。还需要将每一个节点都需要反转一下p.next.next p注意这里需要将 p.next 暂时 置为 null p.next null否则会陷入死循环中。
代码如下 //用递归实现链表反转public Node reverseRecursion(Node p) {if (p.next null) {return p;}Node last reverseRecursion(p.next);p.next.next p;p.next null;return last;} 用递归实现链表反转是其中一种的方法还有四种方法可以实现链表反转需要了解可以点击一下链接Java 算法篇-深入了解单链表的反转实现用 5 种方式来具体实现-CSDN博客 2.3 实现判断回文链表 - 使用快慢指针与反转链表方法 具体思路为先找到链表中的中间节点例如链表 1 - 2 - 3 - 2 - 1 - null 需要先找节点值为3 的节点可以用快慢指针来实现找中间节点。然后将该节点后面的链表( 3 - 2 - 1 - null )进行反转可以用递归来实现反转的链表得 1 - 2 - 3 - null 。接着用旧链表进行与反转后的链表遍历比较若出现不相同值的节点则判断该链表不是回文链表若遍历完都没有返回 false 则判断该链表为回文链表。
代码如下 //查找链表中的中间的节点(快慢指针):假如为奇数则需要找到中间的节点// 假如是偶数则需要找到中间的两个节点的后一个节点。public Node searchMidNode() {//判断是否为空链表if (this.sentry.next null) {return null;}Node fast this.sentry.next;Node slow this.sentry.next;while (fast! null fast.next ! null) {fast fast.next.next;slow slow.next;}return slow;}//用递归实现链表反转public Node reverseRecursion(Node p) {if (p.next null) {return p;}Node last reverseRecursion(p.next);p.next.next p;p.next null;return last;}//判断是否为回文链表public boolean isPalindromeList() {Node p this.sentry.next;//需要先找到中间节点Node midNode this.searchMidNode();//然后将中间节点往后的链表进行反转反转可以用递归的方法。Node newMidNode reverseRecursion(midNode);//接下来就要对旧节点的前半段链表进行循环遍历来比较了每一个节点的值是否相同了//当且仅当当迭代到反转后的链表的最后一个为 null 时结束循环while (newMidNode ! null) {if (p.value ! newMidNode.value) {return false;}p p.next;newMidNode newMidNode.next;}return true;} 需要注意的是对与 p 链表来说一旦实现了链表反转 p 自身的链表会改变。反转之后的链表 newMidNode null 时就该结束循环了。而不能以 p null 作为结束循环条件原因是当链表的节点为偶数时那么反转后的链表会比 p 链表少一个节点假如用 p null 作为结束循环的条件那么当链表的节点数为偶数时肯定会报 空指针异常所以需要以 newMidNode null 作为循环结束条件。 3.0 判断环链表说明 环链表是指链表中至少有一个节点的 next 指针指向了链表中的一个已经存在的节点使得链表中存在环形结构。换句话说链表中的一个节点的 next 指针指向了之前的某个节点导致链表中存在环。 3.1 实现判断环链表与寻找环入口节点 - 龟兔赛跑算法实现 具体思路先来判断是否为环链表可以比作为龟与兔的实际情景当龟每一次走一步时兔每一次走两步。即在相同时间下兔所走的路程时龟的两倍。 情况一当兔第一次没有追上龟时则不是环链表直接返回 null 。 情况二当兔第一次追上了龟时可以判断为该链表为环形链表。接着寻找环入口步骤为可以借助兔子来记录第一次相遇的节点对于龟来说移到头节点开始一步步走同时兔子这次也是一步步走当他们第二次相遇时当前节点就为环入口节点。
代码如下 //判断是否闭环如果是返回则返回换入口如果不是则返回 nullpublic Node isLoop() {Node fast this.sentry.next;Node slow this.sentry.next;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) {slow this.sentry.next;//特例当链表成为一个大环的时候(头尾相连),则直接返回//再相遇即为换入口节点while (true) {if (slow fast) {return slow;}slow slow.next;fast fast.next;}}}//从循环出来的不是闭环return null;} 需要注意的是当该链表是首尾相连时第一次相遇时不用再走第二次了因为此时正好是环入口节点直接返回当前节点。因此第一次相遇之后将龟移到头节点处接着就要判断此时龟与兔此时是否为同一个节点。否则将龟移到头节点处后没有先判断龟与兔是否为同一个节点而将龟、兔同时走向下一步时就会进入判断 if(slow fast)返回已经相对与环节点的下一个的节点。 3.2 解释为什么第一次相遇后兔、龟每一次都走一步最终会相遇且该节点是环入口节点的原因 假设起点到环入口点的距离为 a 个节点n 为在环中转的圈数k 为在圈中走的节点数(可以理解为不够一圈的余数)。可以得出一条公式h a n 无论 n 为多少h 都会刚好来到环入口处。 那么在龟、兔第一次相遇时对于龟来说走了 g a n1 k对于兔来说走了 t a n2 k对于 n1 n2 来说是多少都不在乎但是两者的 k 、a 是一样的。上面说到在第一次相遇的时候兔所走的距离恰好是龟的距离的两倍则龟走的距离 兔走的距离 - 龟走的距离由此可得相当与将龟走的距离换算为圈数 g t - g n2 - n1 g n3n3 具体是多少圈不在乎反正知道是走了圈数那么结合 a n 永远走到的是环入口节点那么 n3 再加上 a 是不是也会走到环入口处 所以此时利用兔在与龟的第一次相遇的节点与龟重新移回头节点处接着龟与兔每一次走一步知道他们相遇时所在的节点即为环入口节点。 4.0 实现判断回文链表、判断环链表且寻找环入口节点的完整代码 import java.util.Iterator;public class List implements IterableInteger{private final Node sentry;static class Node {public int value;public Node next;public Node() {}public Node(int value, Node next) {this.value value;this.next next;}Overridepublic String toString() {return Node{ value value };}}//外部类构造器初始化哨兵节点public List() {sentry new Node(-1,null);}//头插节点public void addFirst(int value) {this.sentry.next new Node(value,this.sentry.next);}//尾插节点public void addLats(int value) {Node p this.sentry;while (p.next ! null) {p p.next;}p.next new Node(value,null);}//重写迭代器Overridepublic IteratorInteger iterator() {return new IteratorInteger() {Node p sentry.next;Overridepublic boolean hasNext() {return p ! null;}Overridepublic Integer next() {int k p.value;p p.next;return k;}};}//查找链表中的中间的节点(快慢指针):假如为奇数则需要找到中间的节点// 假如是偶数则需要找到中间的两个节点的后一个节点。public Node searchMidNode() {//判断是否为空链表if (this.sentry.next null) {return null;}Node fast this.sentry.next;Node slow this.sentry.next;while (fast! null fast.next ! null) {fast fast.next.next;slow slow.next;}return slow;}//判断是否为回文链表public boolean isPalindromeList() {Node p this.sentry.next;//需要先找到中间节点Node midNode this.searchMidNode();//然后将中间节点往后的链表进行反转反转可以用递归的方法。Node newMidNode reverseRecursion(midNode);//接下来就要对旧节点的前半段链表进行循环遍历来比较了每一个节点的值是否相同了//当且仅当当迭代到反转后的链表的最后一个为 null 时结束循环while (newMidNode ! null) {if (p.value ! newMidNode.value) {return false;}p p.next;newMidNode newMidNode.next;}return true;}//用递归实现链表反转public Node reverseRecursion(Node p) {if (p.next null) {return p;}Node last reverseRecursion(p.next);p.next.next p;p.next null;return last;}//判断是否闭环如果是返回则返回换入口如果不是则返回 nullpublic Node isLoop() {Node fast this.sentry.next;Node slow this.sentry.next;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) {slow this.sentry.next;//特例当链表成为一个大环的时候(头尾相连),则直接返回//再相遇即为换入口节点while (true) {if (slow fast) {return slow;}slow slow.next;fast fast.next;}}}//从循环出来的不是闭环return null;}}
