【腾讯】环形链表(证明有环)_环形链表有环

1. 题目描述

题目链接：环形链表

2. 题目解析

1. 对于这种问题，最好的做法是~~~~做过一遍~ _ ~
2. 简单来说，定义两个指针，一个快指针，一个慢指针，如果他们能够相遇的话，就代表该链表有环，否则如果快指针走到了null，则证明无环。
3. 这里说明下关于有环的证明：我们的快指针走2步，慢指针走1步，快指针会先在环里进行循环走，等到慢指针也走进环里时。根据速度的相对，如果以满指针为参考系的话，快指针一次走一步，迟早会追上慢指针。

3. 题目代码

public class Solution {
    public boolean hasCycle(ListNode head) {
       if(head == null){
           return false;
       }
       ListNode p1 = head;
       ListNode p2 = head;
       while(p2.next != null && p2.next.next != null){
           p1 = p1.next;
           p2 = p2.next.next;
           if(p1 == p2){
               return true;
           }
       }
       return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17