LeetCode 环形链表【快慢指针】

灰太狼 2022-09-09 15:50 171阅读 0赞

# 1 题目描述 #

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

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

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

进阶：

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

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_18_color_FFFFFF_t_70_g_se_x_16]

# 2 解题 #

## 2.1 Set ##

public boolean hasCycle(ListNode head) { 
            if (head == null) { 
                return false;
            }
            Set<ListNode> set = new HashSet<>();
            ListNode index = head;
            do { 
                if (set.contains(index)) { 
                    return true;
                }
                set.add(index);
                index = index.next;
    
            } while (index != null);
            return false;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

## 2.2 快慢指针 ##

public boolean hasCycle(ListNode head) { 
    
            if (head == null) { 
                return false;
            }
            ListNode slow = head;
            ListNode fast = head;
            do { 
                slow = slow.next;
                if (fast.next == null) { 
                    return false;
                }
                fast = fast.next.next;
    
            } while (fast != null && slow != fast);
    
            return slow == fast;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/9db4581f0fb74000a1a3a9f90c813207.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/cad4c354db46454cbda3cfb05d90b6a7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/16f336510b1f438c92b132c0eb9ac949.png