剑指Offer（五十五）-- 链表中环的入口节点
Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution
题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
给定的链表节点的结构：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
思路以及解答
第一种是直接使用hashSet,遍历链表的时候，如果hashSet中不包含，则添加到HashSet中，如果链表中包含，说明已经回到环的第一个节点。代码实现如下：
public ListNode EntryNodeOfLoop(ListNode pHead) {
HashSet set = new HashSet();
while(pHead!=null){
if(set.contains(pHead)){
return pHead;
}else{
set.add(pHead);
pHead = pHead.next;
}
}
return null;
}
当然，上面的做法时间复杂度为O(n)，由于借助了一个hashSet，空间复杂度也为O(n)。
那假设我们不需要使用额外的空间呢？怎么做呢？
使用快慢双指针，一个一次走一步，一个一次走两步,当两个重合在一起的时候，这时候，并不是环的入口节点。只能说明两个指针，一个比另外一个多走了若干圈，可能是一圈，可能是2，3，3圈。
比如上面的，如果开始节点是A，环的入口是B，相遇的节点是C，那么慢指针走的应该是：S= AB+BC
快指针走的是：2S = AB+(BC+CB)*n+BC，假设多走了n圈
2(AB+BC) = AB+(BC+CB)*n+BC
AB+BC = (BC+CB)*n
假设n =1，那么AB = CB,也就是当前位置到环的入口的长度，等于链表头到环的入口的位置。
因此相遇之后，我们讲一个快指针移动到链表头，两个指针每次一步，直到相遇，这个时候，相遇的节点就是换的入口节点。
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode quick = pHead;
ListNode slow = pHead;
while (quick != null && slow.next != null) {
quick = quick.next;
slow = slow.next.next;
if (quick == slow) {
quick = pHead;
while (quick != slow) {
quick = quick.next;
slow = slow.next;
}
return quick;
}
}
return null;
}
【作者简介】：
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。
平日时间宝贵，只能使用晚上以及周末时间学习写作
腾讯云开发者
