题目描述（简单难度）

141. Linked List Cycle - 图1

判断一个链表是否有环。

解法一

最直接的方法，遍历链表，并且把遍历过的节点用 HashSet 存起来，如果遍历过程中又遇到了之前的节点就说明有环。如果到达了 null 就说明没有环。

  1. public boolean hasCycle(ListNode head) {
  2.     HashSet<ListNode> set = new HashSet<>();
  3.     while (head != null) {
  4.         set.add(head);
  5.         head = head.next;
  6.         if (set.contains(head)) {
  7.             return true;
  8.         }
  9.     }
  10.     return false;
  11. }

解法二

学数据结构课程的时候，应该都用过这个方法，很巧妙，快慢指针。

原理也很好理解，想象一下圆形跑道，两个人跑步，如果一个人跑的快，一个人跑的慢，那么不管两个人从哪个位置出发，跑的过程中两人一定会相遇。

所以这里我们用两个指针 fast 和 slow。fast 每次走两步，slow 每次走一步，如果 fast 到达了 null 就说明没有环。如果 fast 和 slow 相遇了就说明有环。

  1. public boolean hasCycle(ListNode head) {
  2.     ListNode slow = head;
  3.     ListNode fast = head;
  4.     while (fast != null) {
  5.         if (fast.next == null) {
  6.             return false;
  7.         }
  8.         slow = slow.next;
  9.         fast = fast.next.next;
  10.         if (fast == slow) {
  11.             return true;
  12.         }
  13.     }
  14.     return false;
  15. }

总

比较简单的一道题了，快慢指针的思想，也比较常用，很巧妙。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情