链表是否有环

墨蓝 2022-12-03 15:46 165阅读 0赞

# 链表是否有环 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/linked-list-cycle/

## 2、题目要求 ##

> **题目描述**

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

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

> **示例 1：**

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

![image-20200903232201479][]

> **示例 2：**

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

![image-20200903232218278][]

**示例 3：**

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

![image-20200903232229621][]

> **进阶：**

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

## 3、代码思路 ##

方法一：哈希表

我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表，判断是否重复还是属 `HashSet` 最好用

我刚开始还在想，使用 `HashMap`、`HashSet` 不是需要重写 `equals()` 方法和 `hashCode()` 方法吗？后面想明白了，`hashCode()` 方法没重写前，不就是对象的内存地址映射吗？

没有重写 `hashCode()` 方法的话，不同的对象(节点) `hash` 值肯定不同，所以我们判断节点的内存地址是否相同，来判断两个节点是否为同一个节点，所以说，在 `HashSet` 中我们存放的是节点对象的内存地址，对于不同的节点对象，内存地址肯定不同

程序流程：我们遍历整个链表，如果当前结点的引用已经存在于哈希表中，那么返回 `true`（即该链表为环形链表）；如果遍历完整个链表，并没有相同的节点，则证明该链表不是环形链表

--------------------

方法二：快慢指针

要求空间复杂度为 O(1) 的话，我们只能在原链表的基础上操作，我们定义两个指针：慢指针 `slow` 和快指针 `fast`，`slow` 每次走一步，`fast` 每次走两步

我们遍历链表，只要链表有环，`slow` 和 `fast` 便会进入到一个环中，永远不可能为 `null`，并且 `slow` 和 `fast` 总会相遇，这就好比是在操场跑步的两个人，一个跑得慢(`slow`)，一个跑得快(`fast`)，跑得慢的人总会被跑得快的人超圈

## 4、代码实现 ##

方法一：哈希表

class Solution {
        
        public boolean hasCycle(ListNode head) {
        
            ListNode curNode = head;
            Set<ListNode> nodesSeen = new HashSet<>();
            while (curNode != null) {
        
                if (nodesSeen.contains(curNode)) {
        
                    return true;
                } else {
        
                    nodesSeen.add(curNode);
                }
                curNode = curNode.next;
            }
            return false;
        }
    }
    
    // 再次强调，未重写 hashCode() 方法，则 hashCode() 方法返回的是对象所在的内存地址
    class ListNode {
        
        int val;
        ListNode next;
    
        ListNode(int x) {
        
            val = x;
            next = null;
        }
    }

方法二：快慢指针

class Solution {
        
        /**
         * 双指针法判断链表是否有环
         * @param head 链表头结点
         * @return true：链表有环；false：链表没有环
         */
        public boolean hasCycle(ListNode head) {
        
            ListNode slow = head;
            ListNode fast = head;
    
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast){
        
                    return true;
                }
            }
    
            return false;
        }
    }
    
    class ListNode {
        
        int val;
        ListNode next;
    
        ListNode(int x) {
        
            val = x;
            next = null;
        }
    }

[image-20200903232201479]: /images/20221123/2637892ed6fa4babbe7c4bfdfd603bca.png
[image-20200903232218278]: /images/20221123/aef5f3b06f984525a1dcabdfdda17465.png
[image-20200903232229621]: /images/20221123/cd246ef3c1324f798cff5349f26e1324.png