更多题解，关注公众号《程序员学长》，让你进大厂不走弯路

判断链表是否有环

问题描述

LeetCode141. 环形链表

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

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

示例：

输入：head = [-1,-7, 7,-4, 9, 6, -5, -2], pos = 3

输出：true

解释：链表中有一个环，其尾部连接到第二个节点。

分析问题

拿到这个问题，我们最直观的想法就是在遍历结点的过程中去标记一下这个结点是否已经被访问过。如果被访问过，那么就代表该链表有环，直接返回。如果没有被访问过，我们就标记一下，然后接着去遍历下一个结点，直到遍历完整个链表为止。下面我们来看一下代码的实现。

def hasCycle(self, head):
    tags = set()
    while head:
        #表示已经被访问过了，代表有环
        if head in tags:
            return True
        tags.add(head)
        head = head.next
    return False

我们可以知道该算法的时间复杂度和空间复杂度都是O(n)。那我们有更好的解法吗？

优化

你可以这么思考，当有两名同学在操场上以不同的速度进行跑步，它们最终肯定会相遇。因为操场是环形的，如果在直线上跑，那他们肯定不会相遇。

我们假设同学1以速度1在跑，同学2以速度2在跑。

下面我们来看一下代码如何实现。

def hasCycle(self, head):
    #如果链表为空或者链表只有一个结点
    #直接返回false,因为不可能有环
    if not head or not head.next:
        return False
    #快慢指针
    slow = fast = head
    start = True

    while slow != fast || start:
        start=False
        if not fast or not fast.next:
            return False
        slow = slow.next
        fast = fast.next.next

    return True

我们这里引入了一个变量start表示是否是起跑。

可以看到该算法的空间复杂度降低为O(1)。