LeetCode-环形链表(java实现)

逃离我推掉我的手 2022-02-01 23:43 155阅读 0赞

## 题目如下 ##

**本篇文章讨论的都是单链表**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Zlbmdwb2ppYW4_size_16_color_FFFFFF_t_70]  
环形链表就是循环链表的意思。即链表的尾节点不是null，而是重新指向链表的其他节点。  
![一个循环链表][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Zlbmdwb2ppYW4_size_16_color_FFFFFF_t_70 1]  
判断一个**单链表**是否是循环链表，可以采用快慢指针，追击相遇的方式来实现。算法的原理可以形象的比喻成“龟兔赛跑”。兔子的速度是乌龟的两倍，它们在一个环形的跑道上面赛跑。经过一段时间之后，兔子必定会超过乌龟一圈，然后相遇。我们循环一个单链表，如果这个单链表是循环链表，快指针和慢指针必然会在某个节点相遇。

具体的数学证明，请参看这篇博文： [https://blog.csdn.net/mucaoyx/article/details/81395782][https_blog.csdn.net_mucaoyx_article_details_81395782]

以下是运行过程图以及实现代码。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Zlbmdwb2ppYW4_size_16_color_FFFFFF_t_70 2]

/**
     * Definition for singly-linked list.
     * class Node {
     *     int val;
     *     Node next;
     *     Node(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
        public boolean checkCircle(Node list){
        
            if(list == null){
        
                return false;
            }
            Node fast = list.next;
            Node slow = list;
            while (fast != null && fast.next != null){
        
                fast = fast.next.next;
                slow = slow.next;
                if(slow == fast){
        
                    return true;
                }
            }
            return false;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Zlbmdwb2ppYW4_size_16_color_FFFFFF_t_70]: /images/20220202/2be5cf40a9a64c94955ab418d5143322.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Zlbmdwb2ppYW4_size_16_color_FFFFFF_t_70 1]: /images/20220202/c884202307824631a20b72420320fd90.png
[https_blog.csdn.net_mucaoyx_article_details_81395782]: https://blog.csdn.net/mucaoyx/article/details/81395782
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Zlbmdwb2ppYW4_size_16_color_FFFFFF_t_70 2]: /images/20220202/231fcadd5c194d9286e04665fb8a61b0.png