449，快慢指针解决环形链表

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

Above all, don't lose hope.

总之，不要失去希望。

问题描述

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

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

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

示例 2：

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

示例 3：

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

快慢指针解决

判断链表是否有环应该是老生常谈的一个话题了，最简单的一种方式就是快慢指针，慢指针针每次走一步，快指针每次走两步，如果相遇就说明有环，如果有一个为空说明没有环。代码比较简单

 1public boolean hasCycle(ListNode head) {
 2    if (head == null)
 3        return false;
 4    //快慢两个指针
 5    ListNode slow = head;
 6    ListNode fast = head;
 7    while (fast != null && fast.next != null) {
 8        //慢指针每次走一步
 9        slow = slow.next;
10        //快指针每次走两步
11        fast = fast.next.next;
12        //如果相遇，说明有环，直接返回true
13        if (slow == fast)
14            return true;
15    }
16    //否则就是没环
17    return false;
18}

到这里问题好像并没有结束，为什么快慢指针就一定能判断是否有环。我们可以这样来思考一下，假如有环，那么快慢指针最终都会走到环上，假如环的长度是m，快慢指针最近的间距是n，如下图中所示

快指针每次走两步，慢指针每次走一步，所以每走一次快慢指针的间距就要缩小一步，在图一中当走n次的时候就会相遇，在图二中当走m-n次的时候就会相遇。

存放到集合中

这题还可以把节点存放到集合set中，每次存放的时候判断当前节点是否存在，如果存在，说明有环，直接返回true，比较容易理解

 1public boolean hasCycle(ListNode head) {
 2    Set<ListNode> set = new HashSet<>();
 3    while (head != null) {
 4        //如果重复出现说明有环
 5        if (set.contains(head))
 6            return true;
 7        //否则就把当前节点加入到集合中
 8        set.add(head);
 9        head = head.next;
10    }
11    return false;
12}

逐个删除

一个链表从头节点开始一个个删除，所谓删除就是让他的next指针指向他自己。如果没有环，从头结点一个个删除，最后肯定会删完，如下图所示

如果是环形的，那么有两种情况，一种是o型的，一种是6型的。原理都是一样，我们就看一下o型的

如上图所示，如果删到最后，肯定会出现head=head.next；

 1public boolean hasCycle(ListNode head) {
 2    //如果head为空，或者他的next指向为空，直接返回false
 3    if (head == null || head.next == null)
 4        return false;
 5    //如果出现head.next = head表示有环
 6    if (head.next == head)
 7        return true;
 8    ListNode nextNode = head.next;
 9    //当前节点的next指向他自己，相当于把它删除了
10    head.next = head;
11    //然后递归，查看下一个节点
12    return hasCycle(nextNode);
13}