环形链表

2019年2月4日算法题

---

1，环形链表判断

（1）双指针法

        双指针法的思想：定义fast、slow两个节点，都从头节点开始遍历，fast节点每次向前移动两个节点(fast = fast.next.next)，slow节点每次向前移动一个节点(slow = slow.next)

        如果无环，fast节点在到达链表末尾的时就会停下，程序结束；

        如果有环，fast节点从链表末尾指向的节点继续循环，在经历一定次数的循环之后，fast节点和slow节点相交，此时程序结束。

代码示例：

图1 双指针法 代码示例

---

（2）Hash表法

        Hash表法，使用HashSet进行实现，从头节点开始，将已经遍历过的节点放入到hashSet中，在后续遍历中判断是否有相同节点。

图2 hash表法 代码示例