141. 环形链表（双指针）（哈希表）_环形链表双指针

方法一：
哈希表

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode p = head;
        while(p!=null){
            if(set.contains(p))
                return true;
            set.add(p);
            p = p.next;
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

方法二：
双指针，设置快慢指针；

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {

        if(head == null || head.next == null) return false;
        ListNode slowPtr = head;

        //如果将fastPtr赋值为head，那么对只有一个节点的情况，无法判断是否有环
        ListNode fastPtr = head.next;

        while(fastPtr!=null && fastPtr.next !=null){
            if(slowPtr == fastPtr) return true;

            slowPtr = slowPtr.next;
            fastPtr = fastPtr.next.next;
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30