标签云
B+树 B-树 C++ C++标准库 HTTP Linux Linux概述 TCP UDP VFS chrome deque heap hexo leetcode list map module pair priority_queue queue set stack string vector 互斥锁 人生 传记 传输层 信号量 关联容器 内存分区 内存分配 内存管理 内核 初始化 动态多态 单例模式 名著 命令 哲学 块设备 基本结构 多态 多线程 大数据 大数据计算 套接字 学术论文 容器类 封装 工具 应用层 建造者模式 心态 性能分析 挑战 插件 操作系统 教程 散列表 数据结构 文件与目录 文件系统 文档和注释 栈 桶排序 概述 模块 浅拷贝 深拷贝 演讲 版本控制 特殊文件系统 生产力 目录结构 研究方法论 硬连接 程序执行 简述 算法 红黑树 练习 继承 编译加载 网络 虚拟文件系统 计算机网络 设计方法 设计模式 说明 诺贝尔奖 调试器 费曼 软连接 运算符 重载 链表 阅读笔记 队列 静态多态 面向对象 音标 顺序容器 驱动程序标签
5 分钟 读完 (大约 682 个字)
环状链表判断算法
判断该链表是否有环
- 采用两个指针，一个用来遍历，一个用来从头到当前遍历位置的数据对比。
思想：比较元素是否出过；
复杂度：时间O(n^2),空间O(1) - hash表的方法，记录元素，一旦在hash表中出现过,就证明有环
复杂度：时间O(n),空间O(n) 双指针类型方法：两个指针p1和p2，让它们同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针p1每次向后移动1个节点，让指针p2每次向后移动2个节点，然后比较
两个指针指向的节点是否相同。如果相同，则可以判断出链表有环，如果不同，则继续下一次循环。
思想：追及问题，让快的先跑，如果有环，快的绕一圈后肯定会追上慢的。
复杂度：时间O(n),空间O(1)