Go语言实现：【剑指offer】链表中环的入口结点
2024-09-25 06:40:22
该题目来源于牛客网《剑指offer》专题。
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
Go语言实现：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
//哈希表
func detectCycle(head *ListNode) *ListNode {
//用map的key来判断是否已经存在
m := make(map[*ListNode]int)
//遍历链表，如果key不存在则赋值，已存在说明有环，遍历一遍后不存在则无环
for head != nil {
_, ok := m[head]
if ok == false {
m[head] = 1
head = head.Next
} else {
return head
}
}
return nil
}
//快慢指针
func detectCycle(head *ListNode) *ListNode {
if head == nil {
return nil
}
//定义两个指针，fast一次走两步，slow一次走一步
fast := head
slow := head
for {
//fast遍历一遍，没有环
if fast.Next == nil {
return nil
}
fast = fast.Next.Next
slow = slow.Next
//快慢相遇，存在环，跳出循环，注意此时并不一定是环入口结点
if fast == slow {
break
}
}
//fast指向开始的地方，一次走一步，直到两者相遇
fast = head
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return fast
}
最新文章
- iOS tableView右滑显示选择
- session在本地可以正常使用，而在sae上却无法使用或者值为空的解决方法
- 64位centos下安装python的PIL模块
- kubernetes 1.3 的安装和集群环境部署
- <php>上传文件的程序
- c# GridView Footor列求合计
- mvc 微软票据验证
- .NET基础笔记（C#）
- git代码回滚
- Dubbox中开发REST风格的远程调用
- windows 终端命令详解
- how to select checkbox on cli environment?
- CopyOnWriteArraySet简介
- Mysql Group by 使用解析
- hive建表报错：Specified key was too long; max key length is 767 bytes，hadoophive
- 201772020113李清华《面向对象程序设计（java）》第一周学习总结
- Java读取oracle数据库中blob字段数据文件保存到本地文件(转载)
- hdoj1003 DP
- chipmunk 物理引擎的基本概念和基本用法
- web开发 那些年基于Redis的Provider库