开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 牛客网面试必刷TOP101之——带环链表 -> 正文阅读

[数据结构与算法]牛客网面试必刷TOP101之——带环链表

??作者简介：即将大四的北京某能源高校学生。
?
📚座右铭：“九层之台，起于垒土” 。所以学习技术须脚踏实地。
?
📖这里推荐一款刷题、模拟面试神器，可助你斩获大厂offer：点我免费刷题、模拟面试

前言

🌏牛客网是一个集笔面试系统、题库、课程教育、社群交流、招聘内推于一体的招聘类网站，更是一个专注于程序员的学习和成长的平台。
?
在某次浏览博客的过程中，我偶然点进一个链接，注册了牛客账号。一来到牛客首页，我就被其丰富的功能与良好的社区环境所吸引：

进入题库，更是有最新校招试题与专项练习：
在线编程更是有在线调试功能，可大大提高debug效率：

问答题下还有超多牛客用户交流：

🔔总之，牛客是一个专注于程序员的学习和成长的平台，所以我极力推荐大家注册牛客，坚持刷题，充实自己，大厂offer便指日可待。

牛客必刷题

?链表，别名链式存储结构或单链表，用于存储逻辑关系为 “一对一” 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。

📚下面来刷几个链表题练练手

1. 判断链表中是否有环

题目：
在这里插入图片描述
示例：

方法一： 使用快慢指针

设置快慢两个指针，初始都指向链表头。
遍历链表，快指针每次走两步，慢指针每次走一步。
如果快指针到了链表末尾，说明没有环，因为它每次走两步，所以要验证连续两步是否为NULL。
如果链表有环，那快慢双指针会在环内循环，因为快指针每次走两步，因此快指针会在环内追到慢指针，二者相遇就代表有环。

C++解题代码：

本着“Talk is cheap. Show me the code”的原则，直接上代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast) return true;
        }
        return false;
    }
};

时间复杂度：假设fast超前slow d 个节点，环周长 C，则需要 C-d 步 fast才能追上 slow。需要的总步数为 n-d。时间复杂度为 $O (n)$ 。

空间复杂度：只需维护fast与slow，空间复杂度为 $O (1)$ 。

在这里插入图片描述
方法二： 逐个删除

一个链表从头节点开始一个个删除，所谓删除就是让他的next指针指向他自己。如果没有环，从头结点一个个删除，最后肯定会删完，如下图所示

参考图片
在这里插入图片描述
如果是环形的，那么有两种情况，一种是o型的，一种是6型的。原理都是一样，我们就看一下o型的：
请添加图片描述
如上图所示，如果删到最后，不论是o型的还是6型的肯定会出现head=head.next。

C++解题代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        while(head && head->next){
            ListNode *next=head->next;
            if(next==head) return true;
            head->next=head;
            head=next;
        }
        return false;
    }
};

在这里插入图片描述
时间复杂度：程序到链表最后一个节点处结束循环，时间复杂度为 $O (n)$ 。

空间复杂度：程序只需维护fast与slow，空间复杂度为 $O (1)$ 。

2. 链表中环的入口结点

题目：
在这里插入图片描述

示例：
在这里插入图片描述
解题方法：

利用上一题的方法二，当上题程序确认程序有环时，head指针刚好走到环的入口处，所以当走到入口时直接返回节点即可得解：

C++解题代码：

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        while(pHead && pHead->next){
            ListNode *next=pHead->next;
            if(next==pHead) return next;
            pHead->next=pHead;
            pHead=next;
        }
        return NULL;
    }
};