数据结构~~带环链表的环开始的节点位置**两种方法

本文主要是介绍数据结构~~带环链表的环开始的节点位置**两种方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.带环链表环开始的位置

（1）上面的这个测试用例使用的是包含了4个节点的带环链表，我们要找的就是链表里面的环开始的节点的位置，拿这个测试用例而言，就是2这个节点，从这个节点开始，我们的链表就形成了一个环，我们要设计程序说明在普适的情况下面如何找到这个环开始位置的节点；

（2）我们这里的思路和之前的一个判断链表是否存在环的相同的思路，我们的快指针肯定会先进入这个环，慢指针后进入这个环，当慢指针进入环的时候，我们的快指针肯定已经在环里面走了好几圈了，我们假设慢指针一次走1步，快指针一次走2步，因为在这个过程中快指针每次都比慢指针多走一步，这个时候就一定是可以追上的；

（3）这个题目的解题方法，其实很简单，但是你可能之前从来没有考虑过这个问题，就是在环上面快慢指针相遇的地方我们设置为meet指针，在开始的位置，我们设置为head指针（注意这里的head指针是指的最开始的位置，下面的图里面有表示），这个时候让meet指针一次走一步，head指针一次走一步，这样进行下去，他们相遇的地方，就是我们的题目里面要求的环的节点的初始位置；是不是很神奇，你可能会问，一定会在这个环的开始节点的位置相遇吗，为什么会这么巧？对就是这样的，一定会相遇的，我们是可以通过数学推演证明出来；

（4）我们利用的等量关系就是快指针走过的路程是慢指针的两倍（这个并不是题目里面给出的，而是我们自己使用的），我们肯定是要在题目里面进行说明的，代码表示就是fast=fast->next->next而慢指针则是slow=slow->next这样表示的就是我们设置的慢指针一次走一步，快指针一次走两步，我们分别表示出来再相遇的时候两个指针各自走过的路程，利用快指针的路程==慢指针路程的两倍进行列式计算，就可以得到一个等量关系，这个等量关系就可以说明meet和head指针相遇的位置就是我们要求的环的初始位置节点；

（5）这个路程的表示还是要使用到这个图，L表示的是没有进环之前走过的路程，N表示的就是慢指针进环到这两个指针相遇走过的路程，我们还是假设这个环上面的节点元素的个数是C，慢指针走过的路程就是进环之前的L加上进环之后的N，快指针走过的路程就是进环之前的L加上（我们假设慢指针进环的时候，快指针已经走过了x圈），x*c还要加上N（这个地方可能比较难以理解，多去领悟吧）；

（6）利用快指针走的路程是慢指针2倍，就可以得到L=x*C-N这个表达式，当这个X=1的时候L==C-N那么就是说head指针进环之前的路程恰好可以让meet指针走过C-N到达环开始节点位置在这个位置相遇，这个我们是可以很直观的看出来的，但是x等于其他的不是一的数字的时候，好像就不是非常直观了；

（7）我们对于原来的式子稍加化简，得到L=（x-1)*C+C-N,这样的话就是说当head指针走过L路程的时候,我们的meet指针走过x-1圈加上C-N这段路程，两者还是会在这个环的初始位置相遇的。

（8）具体的代码如下所示：

下面我们介绍这个题目的第二种方法，因为上面的这个方法虽然简单，但是似乎不容易想到，因为如果我们是第一次做，我们是很难想到的，下面我们介绍的方法是基于我们之前的相交链表实现这个环的头部位置节点的查找：

就是我们现在是相当于把这个环形从meet这个位置断开，让meet->next定义为newhead指针，这个时候meet后面已经没有东西了，所以我们就要把这个meet->next置空；

这个时候就把这个找环开始位置节点的问题，转换为求解两个链表的相交节点，这个相交接点恰好是我们想要查找的环形链表的开始位置的节点（通过上面的图片可以清晰的看出来）；这两个链表一个就是原本的以head为节点的链表，另外的一个就是以我们自己重新进行定义的newhead作为头部节点的链表，我们接下来的工作就是找这两个链表的相交节点；

这个时候我们只需要对于这个程序稍加修改就可以了：修改的地方如下

（1）这个时候我们首先要把meet指针的next节点设置为newhead节点，让后把这个meet->next置空（这个时候newhead是不会受到影响的，因为就相当于是把meet和后面节点的连接给切断了）

（2）我们需要把之前的判断相交节点代码拷贝过来就可以了，然后在这个函数里面调用求解两个链表相交节点的函数，我们需要传递的参数就是head和newhead这两个作为参数；对于这个相交节点的问题，可以看我之前的这个博客，里面有详细的介绍；

链表-----返回倒数第K个节点&&回文结构的判断&&相交链表-CSDN博客https://blog.csdn.net/binhyun/article/details/138368598?spm=1001.2014.3001.5502（3）detectcycle函数里面，我们也是要进行相应的修改的，就是添加meet节点，定义newhead节点，然后把meet->next置空，最后把这个getintersrctionnode这个函数的返回值作为detectCycle函数的返回值就可以了。