leetcode141 -- 环形链表

一、问题描述

给你一个链表的头节点 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;
            
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这是博主自己写的代码，经过观察，发现可以优化，因为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;
            
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这个简化过的方法在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;
1
2
3
4
5
6
7
8
9

• 时间复杂度：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;

            
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这里解释一下为什么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;
1
2
3
4
5
6
7
8
9
10
11
12

注意：

1. fast，slow，head的赋值顺序，一定是head在最后一个位置，将head赋值给fast和slow。
2. 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;
            
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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;
1
2
3
4
5
6
7
8
9
10
11

一定不要忘了节点的迭代，即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;
1
2
3
4
5
6
7
8
9

使用java语言，不能使用这种方法，因为有数据类型的限制。

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

参考：
https://leetcode.cn/problems/linked-list-cycle/solution/