题解 | #判断链表中是否有环#

解题思路

遍历一次链表，在遍历的过程中对每一个节点进行标记--是否已被访问，因为空间复杂度要求O(1)，不允许开辟新的空间，因此不能用hash存储，因此我直接将节点的值用一个固定的数字标识，一开始用-1标识，有1/15的样例不通过，结果发现val范围在10^-5~10^5，因此考虑到五位数字不会超出整数范围，因此用100001标记。

执行用时：88ms，超过6.8%
内存消耗：18MB，超过70.8%

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self , head ):
        # write code here
        # 为每个节点添加标记
        cur = head
        while cur:
            print(cur.val)
            if cur.val != 100001:
                cur.val = 100001
                cur = cur.next
            else:
                return True # 有环
        return False # 无环

快慢指针

题解中 几乎都是快慢指针来操作的，初始化慢指针在head上，快指针在head.next上；
快指针每次跳过一个节点，慢指针逐个访问，当快慢指针相遇，说明存在闭环。

这里需要注意的就是要在next往后找之前，注意判断next是否存在，这也是不存在闭环的特殊情况，碰到任何一个空节点，直接返回没有闭环。因为单链表只有一个指针
执行用时：60ms，超过75.78%
内存消耗：18.2MB，超过25.6%

def hasCycle(self, head):
    if not head or not head.next: # attention！
        return False
    slow = head
    fast = head.next

    while slow != fast:
        if not fast or not fast.next: # Attention!!
            return False
        slow = slow.next
        fast = fast.next.next
    return True

总结

两种方法对比下来，快慢指针在时间上占优势，空间上我的方法稍占优势