有环链表入口问题

有环链表入口问题
当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样为1，则慢指针与“新”指针相遇的地方就是环的入口。

图片来源:黑马程序员

证明:
设a为起点位置，b为入口位置，c为快慢指针相遇节点，则有:
fast_step=ab+bc+n*(bc+cb) [快指针]
slow_step=ab+bc [慢指针]
n>=1,指fast指针走过的圈数，快指针最少要多跑一圈才能追上慢指针slow
因为快指针步长为2，慢指针步长为1，所以有:fast_step=2slow_step
所以有ab+bc+n(bc+cb)=2*(ab+bc)
移项得:ab=(n-1)*(bc+cb)+cb
又因为:bc+cb为环，所以bc+cb=0
所以ab=(n-1)*0+cb=cb
所以在快慢指针相遇时，由头结点和相遇节点同时出发的两个步长为1的节点相遇时的位置即为环入口

代码实现

package com.vmware.test.link;public class QuickPoint<T> {private static class Node<T> {public Node(T data, Node<T> next) {this.data = data;this.next = next;}public Node<T> next;public T data;@Overridepublic String toString() {return "Node{" +"data=" + data +'}';}}/*** 获取环入口** @return*/public static <T> Node<T> entrance(Node<T> first){Node<T> fast = first;Node<T> slow = first;boolean isCircle = false;while (fast != null && fast.next != null) {fast = fast.next.next; //步长为2slow = slow.next;//步长为1if (fast.equals(slow)) {isCircle = true;break;}}if (isCircle) {Node<T> temp = first;while (!temp.equals(slow)) {slow = slow.next;temp = temp.next;}return temp;}return null;}public static void main(String[] args) {Node<Integer> node1=new Node<>(1,null);Node<Integer> node2=new Node<>(2,null);Node<Integer> node3=new Node<>(3,null);Node<Integer> node4=new Node<>(4,null);Node<Integer> node5=new Node<>(5,null);Node<Integer> node6=new Node<>(6,null);Node<Integer> node7=new Node<>(7,null);node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;node5.next=node6;node6.next=node7;node7.next=node3;Node<Integer> entrance = entrance(node1);System.out.println(entrance);}
}