LeetCode-141. 环形链表

1.题目描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例1:
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例2:
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例3:
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

2.分析

• 想到使用两个指针slow和fast分别遍历链表，fast指针遍历的速度是slow的两倍，如果两个指针能重叠，就说明这个链表是有环的。
• 注意点如何判断重叠？is是python中判断两个对象是否是同一个对象（内存地址一致），所以可以用is来判断slow和fast指向的是不是同一个节点。
• 注意边界条件的排除

3.解答

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        可以考虑用两个指针，slow和fast，当这两个指针重叠之后，则表示这个链表有环
        """
        if not head or not head.next:
            return False
        
        slow,fast = head,head
        
        while slow and fast:  # 如果跳出这个循环，说明链表有尽头，无环
            try:  # 用来规避fast.next 就是none这个情况
                slow = slow.next
                fast = fast.next.next
                
                if slow is fast:  # 这一步是关键，可以通过is来判断节点是不是在同一个内存地址里（也就是是否是同一个）
                    return True
                
            except:
                return False
            
        return False

• 或者直接这么写

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        else:
            return False