二狗子

判断单链表是否有环

2020-06-09 · 5 min read
算法 面试

哈希法

思路

链表上面如果有环,那么必然有一个链表靠后的节点的next指针,指向它前面的某个节点。

采用Set,将链表循环,每次循环都判断此节点是否存在于Set中,不存在则加入,存在则有环。

代码

ListNode detectCycle(ListNode head) {
  Set<ListNode> visited = new HashSet<>();
  ListNode node = head;
  while(node != null) {
    if (visited.contains(node))
      return node;
    visited.add(node);
    node = node.next;
  }
}

双指针法(Floyd算法)

思路

使用 2 个指针,快指针每次走 2 步,慢指针每次走 1 步,如果链表有环,那么它们肯定可以在环中相遇。就像两个人在圆形的赛道上赛跑,一个跑的快另一个跑的慢,最终肯定是跑的快的人,追上了跑的慢的。

简单来说,当快、慢两个指针首次相遇后,再用两个指针,指针 A 指向首次相遇的结点,指针 B 移动到单链表的头结点,然后两个指针分别每次向前移动 1 步,最终相遇的地方,就是单链表成环的入口。

我们首先假设环足够大,那么在这道题里,存在 3 个关键结点:链表头结点、环入口结点、快慢指针首次相遇结点。通过这三个点可以将指针移动的路径,分为 3 个区域。

image.png

从前面介绍的思路来说,当找到首次相遇点后,使用两个指针,指针 A 指向首次相遇的点,指针 B 指向链表头,两个指针继续同时向前走,每次走 1 步,最终会在链表环的入口处相遇。

image.png

既然 A、B 两个指针,每次走 1 步,最终相遇的点,就是环的入口,那么从步长来说 F = b,但是为什么它们是相等的呢?Leetcode 給出一个 F = b 的指导公式,很清晰,我贴出来大家参考一下。

image.png

如果公式不好理解,我再用文字描述一下思路。为了简化问题,我们只考虑环很大的情况(后面解释),最少是 2 倍于表头结点到环入口结点的距离。

1. 首先每次快指针走 2 步,慢指针走 1 步,假设慢指针走了 F 步走到了环的入口处,此时快指针走了 2F 步。

2. 当慢指针在环的入口点时,此时快指针距离入口点,已经走了 F 步了,多说一句 F 就是链表头到环入口结点的距离。此时慢指针(slow) 和快指针(fast)都在环上,可将环分为 n(红色)和 b(蓝色) 两个区域,此时 b == F

image.png

3. 接下来快、慢指针继续向前走,快指针想要追上慢指针,只有一种情况,就是慢指针走了 b 步,而快指针走了 2b 步,跨越了环入口结点。可以简单理解这个圆环,以环入口点到圆心为轴,翻转了一次。

image.png

到这里应该就清晰了,剩余的 b 区域,其实就等于 F 区域,所以再用两个指针,分别在相遇结点和头结点继续向前走,每次走 1 步,最终两个指针会在入环点相遇。

代码

public ListNode detectCycle(ListNode head) {
  ListNode slow = head, fast = head;
  while (true) {
    if (fast == null || fast.next == null)
      return null;
    slow = slow.next;
    fast = fast.next.next;
    if (fast == slow)
      break;
  }
  fast = head;
  while (slow != fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return fast;
}

到这里这个问题就说清楚了,不过我看不少人还有一些小疑问,这里也一并解答。

前面说到,为了简化问题,我们的前提条件是环很大,那么在环很小的时候呢?

大与小本身就是一个相对的概念,在链表成环的场景下,我们说环很大的意思是在慢指针走到入环结点时,快指针还没有走完一圈。也就是说,要满足这个条件 2F < C,F 为链表头结点到入环结点的长度,C 为环长度,这里面有两个变量。

这就清晰了,要么真的是个很大的环,要么 F 的长度很短,都可以说是「小环」,此时慢指针走到入环结点时,快指针已经在环内空转了 n 圈了。

环小的情况,其实和环大的情况是一样的,只是人为的觉得快指针多跑了很多圈,好像更复杂一些,这里说两个思考模型,来帮助我们思考。

1. 小环展开成大环。可以将小环循环铺开,虚拟展开成一个大环去理解。

image.png

2. 从单链表上,去掉环内空转的长度。我们其实不关心链表表头到入环结点的实际距离,我们只是为了求入环点,所以可以直接将快指针在环内空转的距离,从单链表上去掉。

image.png

这 2 个思考模型,都是为了帮助我们更好的理解和抽象问题,其实在「小环」的场景下,慢指针走到入环结点时,快指针已经在环内空转了很多圈了,所以其实这并不影响我们计算的结果。

找到入环结点,那么环的长度的算法,就是单链表求长度的算法。

原文
LeetCode