P27. 判断单链表是否有环

leetcode 141 lintcode 102 易 链表 双指针 免费 讨论

温馨提示：如果题目对您来说比较简单，可以采用 1.5 倍速观看。 立即注册观看更多视频

描述

这个题目说的是，给你一个单链表，你要判断它是否会形成环，也就是链表的最后一个节点指向了前面一个已经存在的节点。

代码
public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public boolean hasCycleWithHashSet(ListNode head) {
    Set<ListNode> set = new HashSet<>();
    for (ListNode p = head; p != null; p = p.next) {
      if (set.contains(p)) return true;
      set.add(p);
    }
    return false;
  }

  // Time: O(n), Space: O(1)
  public boolean hasCycleWithTwoPointer(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
      fast = fast.next.next;
      slow = slow.next;
      if (fast == slow) return true;
    }
    return false;
  }

}

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分：题目的剖析讲解以及编码，力求在讲解清楚到位的基础上，尽可能地保持视频精简短小，让大家可以在碎片时间里进行学习，并收获这些算法题背后的思想与乐趣。