个人主页会编程的土豆欢迎来访作者简介后端学习者❄️个人专栏数据结构与算法数据库leetcode✨那些你一个人走过的夜路终将化作照亮未来的光语言Go范围相交 / 反转 / 回文 / 环 / 合并 / 删除 / 两两交换 / K 组反转 / 随机指针复制 / 排序 / 合并 K 条 / LRU目标不只会做题还能说出「这题在练什么指针技巧」写在前面链表题看起来花样多真正反复用的就这几板斧套路干什么代表题虚拟头结点 dummy统一头节点删除/插入边界21、19、24、25、2快慢指针找中点、判环、倒数第 N141、142、19、234、148迭代反转pre/cur/next三指针206、25、234双指针对齐长度差、相交160归并思想有序合并、归并排序21、23、148哈希表随机指针、LRU138、146下面按「先易后难、按套路分组」讲解。结构体统一用type ListNode struct { Val int Next *ListNode }一、基础功反转链表206题意反转整条链表返回新头。思路迭代三指针。func reverseList(head *ListNode) *ListNode { var pre *ListNode cur : head for cur ! nil { next : cur.Next cur.Next pre pre cur cur next } return pre }要记住的口诀先存next再改指向再挪pre/cur。后面 25、234、148 都会用到「局部反转」。二、双指针对齐相交链表160题意两链表若相交返回交点否则nil。节点地址相同才算相交最优思路A 走完接 B 头B 走完接 A 头。若相交第二次会在交点相遇不相交则同时走到nil。func getIntersectionNode(headA, headB *ListNode) *ListNode { if headA nil || headB nil { return nil } p, q : headA, headB for p ! q { if p ! nil { p p.Next } else { p headB } if q ! nil { q q.Next } else { q headA } } return p }为什么对设独有段长a/b公共段c。两边都走abc必然在交点对齐。三、快慢指针环检测3.1 环形链表141——有没有环func hasCycle(head *ListNode) bool { slow, fast : head, head for fast ! nil fast.Next ! nil { slow slow.Next fast fast.Next.Next if slow fast { return true } } return false }快指针一次两步慢指针一步有环必相遇。3.2 环形链表 II142——环入口结论相遇后一个指针回head两个每次走一步再相遇就是入口。func detectCycle(head *ListNode) *ListNode { slow, fast : head, head for fast ! nil fast.Next ! nil { slow slow.Next fast fast.Next.Next if slow fast { p : head for p ! slow { p p.Next slow slow.Next } return p } } return nil }面试可讲设头到入口a入口到相遇b环长c。由2(ab)abkc得akc-b所以从头和相遇点同速走会在入口汇合。四、回文链表234题意判断是否回文。推荐做法O(n) 时间O(1) 额外空间快慢指针找中点反转后半段前后比较func isPalindrome(head *ListNode) bool { if head nil || head.Next nil { return true } slow, fast : head, head for fast.Next ! nil fast.Next.Next ! nil { slow slow.Next fast fast.Next.Next } // slow 是前半尾反转后半 second : reverseList(slow.Next) p1, p2 : head, second ok : true for p2 ! nil { if p1.Val ! p2.Val { ok false break } p1 p1.Next p2 p2.Next } // 可选恢复链表 slow.Next reverseList(second) return ok }五、合并类5.1 合并两个有序链表21dummy 双指针谁小接谁。func mergeTwoLists(l1, l2 *ListNode) *ListNode { dummy : ListNode{} cur : dummy for l1 ! nil l2 ! nil { if l1.Val l2.Val { cur.Next l1 l1 l1.Next } else { cur.Next l2 l2 l2.Next } cur cur.Next } if l1 ! nil { cur.Next l1 } else { cur.Next l2 } return dummy.Next }5.2 合并 K 个升序链表23【Hard】思路 A两两合并分治总复杂度约 O(N log K)。func mergeKLists(lists []*ListNode) *ListNode { if len(lists) 0 { return nil } return mergeRange(lists, 0, len(lists)-1) } func mergeRange(lists []*ListNode, l, r int) *ListNode { if l r { return lists[l] } mid : (l r) / 2 return mergeTwoLists(mergeRange(lists, l, mid), mergeRange(lists, mid1, r)) }思路 B小根堆每次取最小头结点Go 可用container/heap。分治版更贴「会了 21 就能扩」。六、两数相加2链表逆序存数字对应位相加 进位。dummy 从头往后接。func addTwoNumbers(l1, l2 *ListNode) *ListNode { dummy : ListNode{} cur : dummy carry : 0 for l1 ! nil || l2 ! nil || carry ! 0 { sum : carry if l1 ! nil { sum l1.Val l1 l1.Next } if l2 ! nil { sum l2.Val l2 l2.Next } carry sum / 10 cur.Next ListNode{Val: sum % 10} cur cur.Next } return dummy.Next }要点循环条件带上carry ! 0处理最后进位。七、删除倒数第 N 个结点19经典快指针先走 N 步再快慢一起走慢停在待删前驱。用 dummy避免删的是头结点时特判。func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy : ListNode{Next: head} fast, slow : dummy, dummy for i : 0; i n; i { fast fast.Next } for fast.Next ! nil { fast fast.Next slow slow.Next } slow.Next slow.Next.Next return dummy.Next }八、交换与分段反转8.1 两两交换24每次处理两个节点用 dummy 挂链。func swapPairs(head *ListNode) *ListNode { dummy : ListNode{Next: head} pre : dummy for pre.Next ! nil pre.Next.Next ! nil { a : pre.Next b : a.Next pre.Next b a.Next b.Next b.Next a pre a } return dummy.Next }画一次图pre - a - b - ...变成pre - b - a - ...。8.2 K 个一组翻转25【Hard】流程先数够 K 个不够直接返回反转这 K 个接回前后段继续func reverseKGroup(head *ListNode, k int) *ListNode { dummy : ListNode{Next: head} pre : dummy for { // 检查剩余是否还有 k 个 tail : pre for i : 0; i k; i { tail tail.Next if tail nil { return dummy.Next } } nextGroup : tail.Next // 反转 (pre, nextGroup) 之间 // 区间头是 pre.Next尾是 tail headK : pre.Next // 标准区间反转 var newPre *ListNode nextGroup cur : headK for cur ! nextGroup { nxt : cur.Next cur.Next newPre newPre cur cur nxt } pre.Next tail // 反转后 tail 成新头 pre headK // headK 成新尾作为下一段 pre } }记忆先确认长度 → 反转区间 → 移动pre。九、随机链表的复制138每个节点还有Random指针。type Node struct { Val int Next *Node Random *Node }哈希表法好写面试够用func copyRandomList(head *Node) *Node { if head nil { return nil } mp : map[*Node]*Node{} for p : head; p ! nil; p p.Next { mp[p] Node{Val: p.Val} } for p : head; p ! nil; p p.Next { mp[p].Next mp[p.Next] // p.Next 为 nil 时 mp[nil] 为 nil mp[p].Random mp[p.Random] } return mp[head] }进阶 O(1) 空间原节点后插复制节点 → 设 Random → 拆分。课设/博客先掌握哈希版即可。十、排序链表148要求 O(n log n)常数级空间 →归并排序链表版快慢指针拆两半递归排序mergeTwoLists合并func sortList(head *ListNode) *ListNode { if head nil || head.Next nil { return head } slow, fast : head, head var pre *ListNode for fast ! nil fast.Next ! nil { pre slow slow slow.Next fast fast.Next.Next } pre.Next nil // 切断 return mergeTwoLists(sortList(head), sortList(slow)) }这题把「中点 合并有序链表」串起来了很值。十一、LRU 缓存146表面像设计题内核是哈希表 双向链表。哈希O(1) 找节点双向链表维护使用顺序头部最新尾部最旧type LRUCache struct { cap int cache map[int]*DNode head *DNode // 哨兵head.Next 最新 tail *DNode // 哨兵tail.Prev 最旧 } type DNode struct { key, val int prev, next *DNode } func Constructor(capacity int) LRUCache { h, t : DNode{}, DNode{} h.next, t.prev t, h return LRUCache{ cap: capacity, cache: make(map[int]*DNode), head: h, tail: t, } } func (c *LRUCache) Get(key int) int { node, ok : c.cache[key] if !ok { return -1 } c.moveToHead(node) return node.val } func (c *LRUCache) Put(key, value int) { if node, ok : c.cache[key]; ok { node.val value c.moveToHead(node) return } node : DNode{key: key, val: value} c.cache[key] node c.addToHead(node) if len(c.cache) c.cap { oldest : c.removeTail() delete(c.cache, oldest.key) } } func (c *LRUCache) addToHead(node *DNode) { node.prev c.head node.next c.head.next c.head.next.prev node c.head.next node } func (c *LRUCache) removeNode(node *DNode) { node.prev.next node.next node.next.prev node.prev } func (c *LRUCache) moveToHead(node *DNode) { c.removeNode(node) c.addToHead(node) } func (c *LRUCache) removeTail() *DNode { node : c.tail.prev c.removeNode(node) return node }为什么和链表放一起LRU 本质就是「会挪节点的双向链表」。十二、题单对照与建议刷序顺序题号题目难度核心1206反转链表简单三指针221合并两有序简单dummy3141环形链表简单快慢4160相交链表简单双指针对齐5234回文链表简单中点反转619删倒数第 N中等快慢dummy72两数相加中等进位824两两交换中等局部指针改接9142环入口中等数学双指针10148排序链表中等归并1125K 组反转困难分段反转1223合并 K 条困难分治/堆13138随机复制中等哈希映射14146LRU中等哈希双向链表建议已会 206/21/141优先补25、23、138、146题单里常剩这几道每题练完强迫自己说一句「我用的是 dummy / 快慢 / 反转 / 哈希中的哪一个」十三、调试小技巧Gofunc printList(head *ListNode) { for head ! nil { print(head.Val, -) head head.Next } println(nil) }环题别打印死循环LRU 用小容量手推Put/Get序列。写指针题时先画 46 个节点的纸图再写代码比对着编辑器蒙快得多。
)
