信息技术大学
链表
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
链表
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
反转链表全家桶
反转链表是链表界的 Hello World：迭代三指针，进阶是区间与成组反转。
迭代反转
prev/cur/next 三指针，逐个掉头
区间反转
先走到区间前一位，头插法逐个接回
K 个一组
数够 K 个反转一段，不足 K 保持原样
快慢指针找环与中点
慢走一步快走两步：有环必相遇，无环快指针先到头；中点顺手白送。
判环
快慢相遇即有环，快指针到 null 即无环
环入口
相遇后一指针回 head，再相遇处即入口
中点
快指针走到头，慢指针正停在中间
合并有序链表
哑节点起步，逐个摘小的接上：两条合并 O(n+m)，K 条交给分治或堆。
双链合并
虚头加尾插，摘较小节点依次连接
K 链合并
两两分治或小根堆，均为 O(N log k)
虚拟头节点技巧
头节点可能被删被换是万恶之源：加一个哑节点，头部操作与普通节点同权。
统一逻辑
哑节点当假头，删除插入不再特判头部
返回
最终返回 dummy.next，真头怎么变都不怕
重排与相交链表
重排是找中点加反转再拼接；相交是长度对齐后同步走，指针相同即交点。
重排
找中点断开，后半反转，两段交错合并
相交
长链先走掉长度差，再同步比对指针
细节
相交是节点相同，不是节点值相同
本节要点
- ✓反转三指针，区间与成组是变体
- ✓快慢判环找中点，入口靠二次相遇
- ✓合并用虚头，K 条分治或堆
- ✓哑节点消灭头部特判
延伸主题：手写 K 个一组反转推一遍环入口公式
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1环入口的推导为什么成立？
参考答案设头到入口 a、入口到相遇点 b、环长 c：慢走 a+b，快走 a+b+kc，快为慢的两倍得 a+b=kc，即 a=c−b。故从 head 与相遇点同步出发，走 a 步恰在入口相遇。
2为什么链表题最爱考「哑节点」意识？
参考答案它考察边界处理：删头、换头、空链是错误高发区。哑节点把头部操作统一成普通操作，代码更短、分支更少——这是算法与工程一致的好品味。
3K 个一组反转的关键步骤是什么？
参考答案每组先数够 K 个（不足不动），记录组前驱与组尾；标准反转该段后，前驱接新头、组尾接下一组。考验指针记账，先画图再写代码。