当前位置：网站首页>leetcode141 -- 环形链表

leetcode141 -- 环形链表

2022-07-29 17:14:00 【Marry Andy】

文章目录

一、问题描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

示例 3：
在这里插入图片描述

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

提示：
链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个有效索引。

二、解决问题

法一：哈希表（HashSet）

public class Solution {
    
    public boolean hasCycle(ListNode head) {
    
        HashSet<ListNode> hashset = new HashSet<ListNode>();
        while(head != null){
    
            if(hashset.contains(head))
                return true;
            hashset.add(head);
            head = head.next;
        }

        return false;
            
    }
}

这是博主自己写的代码，经过观察，发现可以优化，因为HashSet有个特性，只能加入不重复的元素，那么就可以将contains方法去掉，代码如下：

public class Solution {
    
    public boolean hasCycle(ListNode head) {
    
        HashSet<ListNode> hashset = new HashSet<ListNode>();
        while(head != null){
    
            if(!hashset.add(head))
                return true;
            head = head.next;
        }

        return false;
            
    }
}

这个简化过的方法在leetcode上用python实现后，显示超出时间限制，只能用简化前的方法，代码如下：

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set();
        while head :
            if head in seen:
                return True;
            seen.add(head);
            head = head.next;
        return False;

时间复杂度：O(n)
空间复杂度：O(n)

法二：快慢指针法

public class Solution {
    
    public boolean hasCycle(ListNode head) {
    
        
        ListNode fast = head;
        ListNode low = fast;

        while(fast != null && fast.next != null){
    

            low = low.next;
            fast = fast.next.next;
            if(fast == low)
                return true;
        }
        return false;

            
    }
}

这里解释一下为什么while循环中的判断，只需要判断到fast.next是否为空就可以了，而不用判断fast.next.next是否为空，因为最后一个节点本身的next就指向null。如下图：
在这里插入图片描述

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        fast = slow = head;

        while fast and fast.next:
            slow = slow.next;
            fast = fast.next.next;

            if slow == fast:
                return True;
            
        return False;

注意：

fast，slow，head的赋值顺序，一定是head在最后一个位置，将head赋值给fast和slow。
python中的与为and，要与 java中的&&区别开来。

时间复杂度：O(n)
空间复杂度：O(1)

法三：耍赖法 ---- 节点个数

经过观察，我们发现，节点的个数区间为[0，10000]，这样就诞生了下面的一种解法：

public class Solution {
    
    public boolean hasCycle(ListNode head) {
    
        int n = 0;
        while(head != null){
    
            n++;
            if(n > 10000)
                return true;
            head = head.next;
        }
        return false;
            
    }
}

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        n = 0;
        while head:
            n = n + 1;
            
            if n > 10000:
                return True;

            head = head.next;
        return False;

一定不要忘了节点的迭代，即head = head.next;

时间复杂度：O(n)
空间复杂度：O(1)

法四：耍赖法 ---- 修改节点值

经过仔细阅读题目，我们发现：节点的值区间为[-10^5 ， 10^5 ]，都是数字是吧，哈哈哈哈，那我来个字符串：

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        while(head):
            if(head.val == "Andy"):
                return True;
            else:
                head.val = "Andy";
            head = head.next;
        return False;