Pengjielee's blog

题目

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

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

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

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例：

示例 1：
3 -> 2 -> 0 -> -4 [-> 2]

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

示例 2：
1 -> 2 [-> 1]

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

示例 3：
1 -> null

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

提示：

链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个有效索引。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/linked-list-cycle 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

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

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

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

JS实现

1、哈希表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  const map = new Map();
  while (head != null) {
    if (map.has(head)) {
      return true;
    } else {
      map.set(head, true);
    }
    head = head.next;
  }
  return false;
};

2、快慢指针

var hasCycle = function (head) {
  if (head === null || head.next === null) {
    return false;
  }
  // 定义快慢指针
  let slow = head,
    fast = head.next;

  // 只要快慢指针未相遇，循环一直执行
  while (slow != fast) {
    // 快指针走完链表，退出循环
    if (fast === null || fast.next === null) {
      return false;
    }
    // 慢指针走一步
    slow = slow.next;
    // 快指针走两步
    fast = fast.next.next;
  }
  return true;
};

Go实现

package main

import (
  "fmt"
)

type ListNode struct {
  Val  int
  Next *ListNode
}

func main() {
  l1 := &ListNode{Val: 1}
  node2 := &ListNode{Val: 2}
  node3 := &ListNode{Val: 3}
  node4 := &ListNode{Val: 4}
  node5 := &ListNode{Val: 5}

  //l1: 有环
  l1.Next = node2
  node2.Next = node3
  node3.Next = node4
  node4.Next = node5
  node5.Next = node4

  //l2: 无环
  l2 := &ListNode{Val: 21}
  l2.Next = &ListNode{Val: 22}
  l2.Next.Next = &ListNode{Val: 23}

  fmt.Println(hasCycle1(l1)) //true
  fmt.Println(hasCycle1(l2)) //false
  fmt.Println(hasCycle2(l1)) //true
  fmt.Println(hasCycle2(l2)) //false
}

func hasCycle1(head *ListNode) bool {
  //用map的key来判断是否已经存在
  mapper := make(map[*ListNode]int)
  //遍历链表，如果key不存在则赋值，已存在说明有环，遍历一遍后不存在则无环
  for head != nil {
    _, ok := mapper[head]
    if ok {
      return true
    } else {
      mapper[head] = 1
    }
    head = head.Next
  }
  return false
}

func hasCycle2(head *ListNode) bool {
  fast := head
  slow := head
  for fast != nil && fast.Next != nil {
    fast = fast.Next.Next
    slow = slow.Next
    if fast == slow {
      return true
    }
  }
  return false
}