链表

#链表| 来源: 网络整理| 查看: 265

如何检测一个链表是否有环

有环的链表：

有环的链表是指链表有环路，例如A->B->C->D->E->F->B，遍历的时候B->C->D->E->F->B会形成环路一直循环。

思路：设置一个快指针fast，一个慢指针slow，二者初始都指向链表头，fast一次走两步，slow一次走一步，两个指针同时向前移动，每移动一次，两个指针都要进行比较，如果快指针等于慢指针，则证明这是个有环的单链表，否则如果fast先行到达链表尾部或为NULL，则证明这是个不带环的单链表。

代码实现：

public static boolean isLoop(Node head) { boolean flag = false; Node slow = head; Node fast = head; while(fast != null && fast.next !=null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { flag = true; break; } } if(fast == null || fast.next ==null) { flag = false; } return flag; } 如何找到环的入口点

思路：如果单链表有环，当slow指针和fast指针相遇时，slow指针还没有遍历完链表，而fast指针已经在环内循环n（n>=1）圈了，假设此时slow指针走了s步，fast指针走了2s步，r为fast在环内转了一圈的步数，a为从链表头到入口点的步数，b为从入口点到相遇点的步数，c为从相遇点再走c步到达入口点，L为整个链表的长度。

slow指针走的步数： s = a + b fast指针走的步数： 2s = s + n*r 即：s = n*r 链表的长度： L = a + b + c = a+r 由上可得： a + b = n*r = (n - 1)*r + r 而r = L - a，所以： a + b = (n - 1)*r + L - a a = (n - 1)*r + L - a - b 而L - a - b = c，所以： a = (n -1)*r +c

综上可得：从链表头到环入口点等于(n - 1)循环内环 + 相遇点到环入口点，于是在链表头和环入口点分别设置一个指针，同时出发，每次各走一步，它们必定会相遇，且第一次相遇的点就是环入口点。

代码实现：

public static Node findLoopPort(Node head) { Node slow = head; Node fast = head; //先判断该链表是否有环 while(fast != null && fast.next !=null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { break; } } if(fast == null || fast.next == null) { return null; } //如果链表有环，则将slow设置指向链表头，此时fast指向相遇点，然后同时开始移动，直到两个指针相遇 slow = head; while(slow != fast) { slow = slow.next; fast = fast.next; } return slow; }

【本文地址】

公司简介

联系我们