要判断单链表有没有环, 肯定会判断两个指针是否相等. 而且这两个指针从头结点位置开始走的步数肯定不一样. 可以设两个指针 slow 和 fast.
slow 从头结点开始往后走, 每次走一步, 同时 fast 从头结点开始往后走, 每次走两步. 这两个指针一直往后面走直到 fast 为空, 则单链表无环, 或者 slow 与 fast 相等, 则单链表有环.
这个过程可以保证 slow 会走过所有在它之前的结点, 同时 fast 比 slow 多走的步长从 1 开始每次递增 1, 而且当它们相遇时多走的步长就是环中结点的个数的正整数倍.
代码如下:
public boolean haveIntersectionNode(ListNode head) {
// 空链表和只有一个头链表均不存在环
if(head == null || head.next) return false;
// s 为慢指针, f 为快指针
ListNode s = head.next, f = head.next.next;
// f 指向空则一定存在
while(f != null){
if(f == s) {return true;}
s = s.next;
if(f.next != null){ // 防止空指针异常
f = f.next.next;
}else{
return true;
}
}
return false;
}