目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
判断链表中是否有环
访问量:1372
一、简介
描述
判断给定的链表中是否有环。如果有环则返回true,否则返回false。
要求:空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)
二、解法
分析:双指针(快慢指针),若存在环,则快指针迟早会追上慢指针
实现如下:
/* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * * @param head ListNode类 * @return bool布尔型 */ func hasCycle( head *ListNode ) bool { // write code here if head == nil || head.Next == nil { return false } quickNode := head.Next // 每次移动两格 slowNode := head // 每次移动1格 for quickNode != nil { if quickNode == slowNode { return true } quickNode = quickNode.Next if quickNode != nil { quickNode = quickNode.Next } slowNode = slowNode.Next } return false }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助