环形链表

Leetcode Link: 141. 环形链表 - 力扣（LeetCode） (leetcode-cn.com) 142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)

题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

Attention

• 上述是141题的描述
• 对于142题，其要求无环返回null（即python中的None），有环返回入环节点。

解法一

思路：哈希表（python中可以使用set()）

题解：时间复杂度 $O(N)$，空间复杂度 $O(N)$

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        bucket = set()
        while(head!=None):
            if head in bucket:
                return True
            else:
                bucket.add(head)
                head = head.next
        return False # head就是环的入口

解法二

思路：有环的话，设定快慢指针，两者必然在某一位置会相等，反之快指针会先走到None。

题解：时间复杂度 $O(N)$，空间复杂度 $O(1)$

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
		# 防止快指针报错
        if head == None:
            return False
        if head.next == None:
            return False
        
        dummy = ListNode()
        dummy.next = head
		# 提前走一次，因为head==head
        fast = dummy.next.next
        slow = dummy.next
 
        while(fast!=slow):
	        # 防止报错，有更好的写法吗？
            if fast.next == None:
                return False
            if fast.next.next == None:
                return False
            
            fast = fast.next.next
            slow = slow.next
            
        return True
        # 有环链表II 的补充代码
        # 下面的代码可以直接给出环的入口
        fast = dummy
        while(fast != slow):
            fast = fast.next
            slow = slow.next
        return True # fast 或者 slow 是环入口

需要注意的是，这里快指针一定要走2步，慢指针一定走1步

上述方法中，判断head和head.next是不是None有点啰嗦，可以采用下面的方式

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
		# 防止快指针报错
		# 在这里，我理解的是先执行 not head, 为True的话直接不看后面进入if语句，所以即使head.next不存在也不会报错。
        if not head or not head.next:
            return False
        
        dummy = ListNode()
        dummy.next = head
		# 提前走一次，因为head==head
        fast = dummy.next.next
        slow = dummy.next
 
        while(fast!=slow):
            if not fast.next or not fast.next.next:
                return False
 
            fast = fast.next.next
            slow = slow.next
 
		return True 
		
        # 有环链表II 的补充代码
        # 下面的代码可以直接给出环的入口
        fast = dummy
        while(fast != slow):
            fast = fast.next
            slow = slow.next
        return True # fast 或者 slow 是环入口

启发和联系

对于解法二，属于「Floyd 判圈算法」（又称龟兔赛跑算法）。

题解链接

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 $N$ 轮。