LeetCode刷题之HOT100之环形链表

下午听了音乐剧《梁祝》，深深的被震撼到了，虽然还不懂音乐的情绪表达与故事走向。刚去吃了一碗重庆小面的新品，很一般哈，不太好吃。然后散散步，好久没逛贴吧了，今天去逛逛，映入眼帘的就是研究生吧。点进去后，那真是听取哀声一片呀！大家不是盲审被挂就是被导师PUA，还有一些科研遇到问题的，对自我的怀疑、贬低、极致的失落、绝望。在里面发现了一些和我一样的学长，车大的，研一猛学java，研二水水论文，达到毕业条件，实习，找工作。我的计划也是如此，加油！先把HOT100刷完，做做java项目。马上就要暑假啦！

有时候想讨论一下沉默的大多数，人生的意义是什么。算了，还是先去码头搞点薯条吧，有时候认为自己与众不同，其实也不过是芸芸罢了。Anyway，做题啦！

1、题目描述

2、逻辑分析

遇到这种题目，我不知道怎么办。先去看一下题解。官方题解给出了两种方法：哈希表、快慢指针。先从哈希表来展开吧。

哈希表：使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

3、代码演示

public boolean hasCycle(ListNode head) {
        // 创建一个HashSet用于存储已经访问过的ListNode对象  
        Set<ListNode> seen = new HashSet<ListNode>();
        while(head != null){
        // 尝试将当前节点head添加到HashSet中  
        // 如果head已经存在于HashSet中，说明之前已经访问过这个节点，链表存在循环  
        // HashSet的add方法会在添加成功时返回true，添加失败（即元素已存在）时返回false  
            if(!seen.add(head)){
                // 如果add方法返回false，说明存在循环，直接返回true 
                return true;
            }
            // 将head移动到下一个节点，继续遍历 
            head = head.next;
        }
        // 如果遍历完整个链表都没有找到循环，说明链表没有循环，返回false
        return false;
    }

代码简练，理解起来也不难，时间复杂度：O(n)，空间复杂度：O(n)。

接下来让我们来看看第二种方法：快慢指针。

题解中以通俗的龟兔赛跑故事来描述此算法，大致思路：兔子站在头指针的后一位（即索引为1的位置），龟龟站在头指针上（即索引为0的位置上）。开始跑，兔子每次跑两个位置，而乌龟每次只跑一个位置。那么如果有环，兔子肯定要穿过环与龟龟相遇。由此可以写出算法的相应代码：

public boolean hasCycle(ListNode head) {
        // 如果链表为空或者只有一个节点，那么肯定没有循环
        if(head == null || head.next == null){
            return false;
        }
       // 初始化两个指针，Gui（慢指针）和Tu（快指针）  
       // Gui每次移动一步，Tu每次移动两步 
       ListNode Gui = head;
       ListNode Tu = head.next;
       // 当两个指针不相等时，继续循环  
       // 注意：这里也检查了Tu和Tu.next是否为null，以确保Tu移动两步不会越界
       while(Gui != Tu){
        // 如果快指针Tu或Tu的下一个节点为null，说明链表已经遍历完毕，没有循环
        if(Tu == null || Tu.next == null){
            return false;
        }
        // 慢指针Gui向前移动一步  
        Gui = Gui.next;
        // 快指针Tu向前移动两步 
        Tu = Tu.next.next;
       }
       // 如果循环结束，说明两个指针在某个节点相遇了，即链表存在循环 
       return true;
    }

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

ok啦，两种方法都挺不错，我比较喜欢第二种快慢指针（龟兔赛跑）这一方法，因为故事吸引我。今天的两题完成了。学学java先。补一张小面图片嘿嘿：

大家看着怎么样啊，我是不是有点奇奇怪怪。代码论坛我发这些琐碎的日常。给人一种无病呻吟的苍白感。哈哈哈哈，不说笑了啦！今天周末，早些下班，还得去跑步呢！BYE！