链表的环以及环的入口

1 判断是否有环

使用快慢指针，快指针 fast 每次走两步，慢指针 slow 每次走一步，

• 如果链表存在环，则快指针 fast 与慢指针 slow 一定会在环的某一环节进行相遇
• 如果链表没有环，则快指针一定会走到链表的尽头，且不可能与慢指针 slow 进行相遇

2 找到环的入口

len 表示链表头节点到环入口的距离
x    表示入口结点到fast和slow相遇结点的距离
y    表示换剩下的距离
L    表示环的长度

显然 L =  x + y
当快慢指针相遇时，慢指针走过的距离为  d = len + x ，快指针都过的距离  2d = len + nL +  x，即慢指针走过 len + x 的结点，快指针比慢指针多走了n圈。这里慢指针在环中也可能多走了几圈才相遇的，但是可以不用表示出来。因为快指针的nL表示的就是比慢指针多走的圈数。举例：慢指针如果走 len + x + 2L，快指针走 len + x + 4L 那么就可以写成：慢len + x 快len + x +2L.是等价的。

由      消去 d  可以得到  len = nL - x ，带入 L = x+y 可得 len = (n -1) L+ y；
此时把快指针重新指向链表的起点，快慢指针同时开始走，两者每次都只走一步，那么快指针走过 len 距离时，慢指针从相遇位置走过 （n-1）环的距离再加上 y 的距离，显然就是换的入口点，所以快慢指针一定会在环的入口点位置相遇。

 

代码实现

        /**
	 * 找到环的入口点
	 * 1 先判断链表是否存在环
	 * 2 利用快慢指针先找到相遇的节点，再将快指针指向链表的头节点，然后再找环的入口点
	 */
	public static ListNode getLoopNode(ListNode head) {
		if (head == null || head.next == null) {
			return null;
		}
		ListNode fast = head.next.next;
		ListNode slow = head.next;
		while (fast != null && fast.next != null) {
			if (fast == slow) {// 找打相遇的节点
				fast = head;// 重置fast
				while (fast != slow) {
					fast = fast.next;
					slow = slow.next;
				}
				return fast;
			}
			fast = fast.next.next;
			slow = slow.next;
		}
		return null;
	}

 

 

本文地址：https://blog.csdn.net/guapi_poe/article/details/107887301