牛客TOP101-判断链表中是否有环

朱雀 2024-03-27 19:26 18阅读 0赞

## 前言 ##

本文以Java为语言讲解【判断链表中是否有环】这一题，题目来源【牛客TOP101】

## 题目描述 ##

![在这里插入图片描述][47a939dbbd7640a7b73e2d490e3d2657.png_pic_center]  
输入用例  
![在这里插入图片描述][b0fbdfd0dd2e43e1b3f0b1851e0acfee.png_pic_center]

## 解题思路 ##

### Hash表法 ###

对于这道题，比较容易想到的可能是使用hash表，因为如果是有环，那么就意味着，在遍历过程中，hash表中记录的节点一定会被记录再次访问，那么就可以确定是是否有环

代码实现如下：

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

空间复杂度是O(N)，时间复杂度为O(N)

### 双指针 ###

链表有环问题，比较优秀的解法是使用双指针，也就是使用快慢指针（slow，fast）

快慢指针，快指针每次走两步，慢指针每次走一步，那么快指针的速度就是慢指针的两倍，那么假设有环存在，快指针就必定会在某个点与慢指针相遇

这个我们很容易理解，就像同学之间跑步，A的速度快，B的速度慢，只要圈数足够的情况下，A一点会在跑道上再次和B相遇，只不过A此时比B多跑了一圈。

代码实现如下：

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

可能有些朋友不能理解为什么fast = head.next, slow = head（我一开始就不明白），其实很简单，快慢指针的定义就是前者走两步，后者走一步，一开始二者都在起跑线上，而head就是一步，head.next就是两步，所以初始化上，就是fast = head.next, slow = head，图示如下：  
![在这里插入图片描述][c34ca3e29f1c4ae4aa27801c45ae62db.png_pic_center]

双指针算法的时间复杂度为O(N)，空间复杂度为O(1)

[47a939dbbd7640a7b73e2d490e3d2657.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/9c998ab080cb49e1bb21674e1ddf9021.png
[b0fbdfd0dd2e43e1b3f0b1851e0acfee.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/e5e45d291f094fba9fcaad631de07974.png
[c34ca3e29f1c4ae4aa27801c45ae62db.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/43a68a780e9e460a935a46858b2292a8.png