关于leetcode:完虐算法判断链表是否有环

更多算法题解，请关注公众号《程序员学长》，欢送退出。

判断链表是否有环

问题形容

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)。