欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

链表的环以及环的入口

程序员文章站 2022-03-23 09:11:05
1判断是否有环使用快慢指针,快指针 fast 每次走两步,慢指针 slow 每次走一步,如果链表存在环,则快指针 fast 与慢指针 slow 一定会在环的某一环节进行相遇如果链表没有环,则快指针一定会走到链表的尽头,且不可能与慢指针 slow 进行相遇2 找到环的入口len 表示链表头节点到环入口的距离x 表示入口结点到fast和slow相遇结点的距离y 表示换剩下的距离L 表示环的长度显然 L = x + y当快慢指针相遇时,慢指针走过的距离为 d ......

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

相关标签: 数据结构 链表