算法思想一:双指针

解题思路:

我们使用两个指针,fast 与 slow。
它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇。
图解:

代码展示:

Python版本
class Solution:
    def hasCycle(self , head ):
        # write code here
        if not head:
            return head
        # 双指针  快慢指针
        slow = head
        fast = head
        while slow and fast:
            slow = slow.next
            if fast.next:
                fast = fast.next.next
            else:
                return False
            # 当双指针相遇 即表示指针有环
            if slow == fast:
                return True
        return False

复杂度分析:

时间复杂度O(N):其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时,slow 指针走过的距离不会超过链表的总长度
空间复杂度O(1):额外使用的指针占用常数空间

算法思想二:哈希表

解题思路:

我们遍历链表中的每个节点,并将它记录下来;一旦遇到了此前遍历过的节点,就可以判定链表中存在环。借助哈希表可以很方便地实现
1、遍历链表,并将访问过的结点存储到哈希表中
2、判断结点是否在哈希表中,若存在则返回 true
3、遍历结束,则返回 false

代码展示:

JAVA版本
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode pos = head;
        // 哈希表记录访问过的结点
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            // 判断结点是否被访问
            if (visited.contains(pos)) {
                return true;
            } else {
                // 结点记录添加到哈希表中
                visited.add(pos);
            }
            // 遍历
            pos = pos.next;
        }
        return false;
    }
}

复杂度分析:

时间复杂度O(N):其中 N 为链表中节点的数目。遍历整个链表的结点
空间复杂度O(N):其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。