文章目录

解释为什么第一次相遇后兔、龟每一次都走一步最终会相遇且该节点是环入口节点的原因

4.0

链表是一种常见的数据结构用于存储一系列元素。

链表由节点组成每个节点包含一个数据元素和一个指向下一个节点的指针。

链表可以分为单向链表和双向链表其中单向链表的节点只有一个指针指向下一个节点而双向链表的节点有两个指针分别指向前一个节点和后一个节点。

代码如下

Node(value,this.sentry.next);}//尾插节点public

void

Node(value,null);}//重写迭代器Overridepublic

IteratorInteger

k;}};}}简单对以上代码进行分析将链表进行封装成一个外部类静态内部类则是节点类进行封装。

外部类的成员变量为一个哨兵节点内部类的成员变量为

int

指向下一个节点的引用变量。

外部类实现了头插节点、尾插节点、重写了迭代器等。

2.0

回文链表是指一个链表从头到尾和从尾到头读是一样的也就是说链表的节点值按照顺序排列和逆序排列是相同的。

例如链表

2.1

指针来说每一次循环都要走一步直到退出循环后若链表的节点的数量为奇数时则指向的节点就是中间节点。

若链表的节点的数量为偶数时则指向的节点是中间两个节点的后一个节点。

例如链表

null此时循环结束后slow

//查找链表中的中间的节点(快慢指针):假如为奇数则需要找到中间的节点//

Node

节点一直回归到回归过程结束为止。

还需要将每一个节点都需要反转一下p.next.next

p注意这里需要将

reverseRecursion(p.next);p.next.next

p;p.next

用递归实现链表反转是其中一种的方法还有四种方法可以实现链表反转需要了解可以点击一下链接Java

种方式来具体实现-CSDN博客

的节点可以用快慢指针来实现找中间节点。

然后将该节点后面的链表(

null

。

接着用旧链表进行与反转后的链表遍历比较若出现不相同值的节点则判断该链表不是回文链表若遍历完都没有返回

false

//查找链表中的中间的节点(快慢指针):假如为奇数则需要找到中间的节点//

Node

reverseRecursion(p.next);p.next.next

p;p.next

this.sentry.next;//需要先找到中间节点Node

midNode

this.searchMidNode();//然后将中间节点往后的链表进行反转反转可以用递归的方法。

Node

newMidNode

reverseRecursion(midNode);//接下来就要对旧节点的前半段链表进行循环遍历来比较了每一个节点的值是否相同了//当且仅当当迭代到反转后的链表的最后一个为

null

作为结束循环条件原因是当链表的节点为偶数时那么反转后的链表会比

链表少一个节点假如用

指针指向了链表中的一个已经存在的节点使得链表中存在环形结构。

换句话说链表中的一个节点的

next

具体思路先来判断是否为环链表可以比作为龟与兔的实际情景当龟每一次走一步时兔每一次走两步。

即在相同时间下兔所走的路程时龟的两倍。

null

情况二当兔第一次追上了龟时可以判断为该链表为环形链表。

接着寻找环入口步骤为可以借助兔子来记录第一次相遇的节点对于龟来说移到头节点开始一步步走同时兔子这次也是一步步走当他们第二次相遇时当前节点就为环入口节点。

代码如下

this.sentry.next;//特例当链表成为一个大环的时候(头尾相连),则直接返回//再相遇即为换入口节点while

(true)

fast.next;}}}//从循环出来的不是闭环return

null;}

需要注意的是当该链表是首尾相连时第一次相遇时不用再走第二次了因为此时正好是环入口节点直接返回当前节点。

因此第一次相遇之后将龟移到头节点处接着就要判断此时龟与兔此时是否为同一个节点。

否则将龟移到头节点处后没有先判断龟与兔是否为同一个节点而将龟、兔同时走向下一步时就会进入判断

if(slow

解释为什么第一次相遇后兔、龟每一次都走一步最终会相遇且该节点是环入口节点的原因

个节点n

为在圈中走的节点数(可以理解为不够一圈的余数)。

可以得出一条公式h

为多少h

是一样的。

上面说到在第一次相遇的时候兔所走的距离恰好是龟的距离的两倍则龟走的距离

n3n3

所以此时利用兔在与龟的第一次相遇的节点与龟重新移回头节点处接着龟与兔每一次走一步知道他们相遇时所在的节点即为环入口节点。

4.0

Node(value,this.sentry.next);}//尾插节点public

void

Node(value,null);}//重写迭代器Overridepublic

IteratorInteger

k;}};}//查找链表中的中间的节点(快慢指针):假如为奇数则需要找到中间的节点//

Node

this.sentry.next;//需要先找到中间节点Node

midNode

this.searchMidNode();//然后将中间节点往后的链表进行反转反转可以用递归的方法。

Node

newMidNode

reverseRecursion(midNode);//接下来就要对旧节点的前半段链表进行循环遍历来比较了每一个节点的值是否相同了//当且仅当当迭代到反转后的链表的最后一个为

null

reverseRecursion(p.next);p.next.next

p;p.next

last;}//判断是否闭环如果是返回则返回换入口如果不是则返回

nullpublic

this.sentry.next;//特例当链表成为一个大环的时候(头尾相连),则直接返回//再相遇即为换入口节点while

(true)

fast.next;}}}//从循环出来的不是闭环return

null;}}