
环形链表判断:用快慢指针,别碰指针赋值陷阱
Go 里没有 GC 友好的“环检测 API”,unsafe 或手动改 next 指针会直接绕过逃逸分析,导致不可预测的内存行为。标准解法是 Floyd 判圈算法,但要注意 Go 的结构体字段指针不能 nil 解引用。
- 常见错误现象:
panic: runtime error: invalid memory address or nil pointer dereference—— 忘了在每次fast = fast.Next.Next前检查fast.Next != nil - 必须先判
fast != nil && fast.Next != nil,再移动;slow只需保证非 nil 就能走一步 - 性能上无额外分配,O(1) 空间、O(n) 时间;兼容所有 Go 版本,不依赖
reflect或unsafe
func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
return false
}
内存循环引用:Go 的 runtime.GC() 不解决引用环
很多人以为调用 runtime.GC() 能强制回收环状对象,其实它只触发一次垃圾收集周期,而 Go 的三色标记法本来就能正确处理循环引用——前提是这些对象**真的不可达**。
- 典型误操作:把环中某个节点存进全局 map 或闭包变量,比如
var cache = make(map[string]*ListNode),只要 key 还在,整个环都活 - 真正要查的是“谁持有根引用”,用
pprof抓 heap profile,看runtime.MemStats中HeapInuse持续上涨却没下降 - struct 字段若含
*T,且T又反过来引用父结构,就构成强引用环;应改用弱关联方式(如 ID、字符串键、或显式Close()断开)
手动断环:避免 defer 延迟执行时已失效
想靠 defer 在函数退出前清理环?小心 defer 绑定的是变量副本,不是运行时地址。
- 错误写法:
defer func() { node.Next = nil }()—— 如果node是参数传入的局部指针,defer 闭包捕获的是其初始值,可能早已被改写 - 正确做法是断环逻辑放在明确位置,比如在释放资源前显式赋值:
current.Next = nil,并确保该语句一定执行(不用 defer 包裹) - 如果必须用 defer,得传入指针的指针:
defer func(p **ListNode) { (*p).Next = nil }(ptrToNode),但极易出错,不推荐
测试环形链表:别用 == 比较结构体,要比较地址
写单元测试时,容易误用结构体值比较来验证环是否形成,比如 assert.Equal(t, listA, listB) —— 这比的是字段内容,不是链表拓扑关系。
立即学习“go语言免费学习笔记(深入)”;
- 环检测逻辑本身只关心指针相等性(
slow == fast),所以测试时也要用地址断言,例如require.Same(t, slow, fast) - 构造环时别用字面量初始化:Go 结构体字面量每次都是新实例,
&ListNode{Next: &head}中的&head是复制,不是原地址 - 正确构造方式是先建节点,再用变量赋值连成环:
node1.Next = node2; node2.Next = node1










