题目描述

解题思路

方法一：Set集合

利用Set集合不存放重复元素的性质，我们遍历一次链表，每遍历一个节点就把他加入到Set集合中：

• 如果添加失败，则说明节点重复出现（即存在环），返回true；
• 如果成功遍历链表，就无环，返回false。

方法二：快慢指针

使用两个指针遍历链表，快指针每次前进两步，慢指针每次前进一步：

• 如果链表存在环，快指针一定会于慢指针相遇，当快指针所指节点与慢指针所指节点相等时，就说明存在环，返回true；
• 当快指针指向null时，遍历结束，说明无环，返回false；

代码实现

方法一：Set集合

/**
 * 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) {
        Set<ListNode> set = new HashSet<ListNode>();
        while(head!=null) {
            if(!set.add(head)){
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

方法二：快慢指针

/**
 * 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 slower = head;     //慢指针
        ListNode faster = head.next;    //  快指针
        while(faster!=null && faster.next!=null){   //遍历结束
            if(slower == faster){       //快慢指针相遇，存在环
                return true;
            }
            slower = slower.next;       //慢指针前进一步
            faster = faster.next.next;  //快指针前进两步
        }
        return false;
    }
}