02.3.1.1 单链表基础操作与反转
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.1 链表
02.3.1.1-001 链表与数组有什么区别?
一句话结论
链表节点离散存储、靠指针串联,插入删除 O(1)(已知节点),随机访问 O(n);数组连续存储、随机访问 O(1),中间增删 O(n)。
概念解释
- 链表:无连续地址,指针跳转。
- 数组:连续内存,下标寻址。
- 选型看主要操作是访问还是增删。
原理流程
- 列出高频操作:查、插、删、遍历。
- 对照两结构代价。
- 按约束选择。
代码 / 图示
链表:node → node → node
数组:[ ][ ][ ][ ] 连续
常见误区
- 误区:链表插入都是 O(1);正解:已知待插位置前驱才 O(1),查找前驱本身 O(n)。
- 误区:链表省内存;正解:每节点指针额外占空间,且缓存局部性差。
追问
- Q:链表随机访问第几项? A:O(n),沿指针遍历。
- Q:频繁中间插入选什么? A:链表;频繁按下标访问选数组。
02.3.1.1-002 单链表节点怎么定义?
一句话结论
节点含值域与 next 指针;头节点指向首元节点,空链表头为 null;题目通常给定节点类,面试先确认是否有哑节点。
概念解释
- val:数据。
- next:后继引用。
- 尾部 next = null。
原理流程
- 定义节点结构。
- 头指针定位链表。
- 末尾以 null 结束。
代码 / 示例
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
常见误区
- 误区:把首元节点当头节点;正解:哑节点是额外哨兵,首元节点存数据。
- 误区:循环忘记判 next 为 null;正解:遍历条件同时判当前节点。
追问
- Q:双向链表节点多什么? A:prev 前驱指针。
- Q:节点值可为重复吗? A:可以,相等判断按 val。
02.3.1.1-003 怎么遍历单链表?
一句话结论
用游标从 head 沿 next 走到 null;遍历时不移动 head,保留头指针;O(n) 时间 O(1) 空间。
概念解释
- 游标:临时指向当前节点。
- 终止:next 为 null。
- 头指针保留:结果返回与入口使用。
原理流程
- cur = head。
- cur 非空处理,cur = cur.next。
- 到 null 结束。
代码 / 示例
for (ListNode cur = head; cur != null; cur = cur.next) {
// 处理 cur.val
}
常见误区
- 误区:直接移动 head 遍历;正解:head 被改掉后无法再定位链表。
- 误区:访问 cur.next.val 前不判空;正解:先判 cur.next 非空。
追问
- Q:遍历求长度? A:计数器累加,O(n)。
- Q:遍历时要删除节点? A:需前驱指针,见删除相关题。
02.3.1.1-004 反转单链表迭代版(LC 206)怎么做?
一句话结论
三指针 prev、cur、next:逐节点把 cur.next 指向 prev,整体后移;O(n) 时间 O(1) 空间,返回 prev 为新头。
概念解释
- 局部反转:改一条指针方向。
- next 保存后继,防断链。
- prev 最终是新头。
原理流程
- prev=null,cur=head。
- 存 next,cur.next=prev,prev=cur,cur=next。
- cur 为 null 时返回 prev。
代码 / 示例
public ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
常见误区
- 误区:先改 cur.next 再存 next;正解:先存后继再改指针。
- 误区:返回 head;正解:head 变尾部,新头是 prev。
追问
- Q:空链表/单节点? A:循环不执行,返回 prev(null 或原节点)。
- Q:反转后原头指向? A:成为尾部,next 为 null。
02.3.1.1-005 反转链表递归版怎么写?
一句话结论
递归反转后继段得到新头,再把当前节点接到新段尾部,当前节点 next 置 null;O(n) 时间 O(n) 递归栈空间。
概念解释
- 子问题:反转 head 之后的链表。
- 拼接:head 接到后继段末尾。
- 基准:空或单节点直接返回。
原理流程
- 基准 head 为空/单节点返回。
- 递归反转后继得 newHead。
- head.next.next = head,head.next = null。
代码 / 示例
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
常见误区
- 误区:忘记 head.next=null;正解:否则首尾形成环。
- 误区:递归深度过大栈溢出;正解:长链表改迭代。
追问
- Q:递归空间复杂度? A:O(n) 调用栈。
- Q:递归返回的新头是什么? A:原链表尾节点。
02.3.1.1-006 反转前 N 个节点怎么做?
一句话结论
递归记录第 N+1 个节点作为后继,前 N 个反转后头部接到该后继;迭代版用头插法逐节点插到反转段头部。
概念解释
- 截断点:第 N+1 节点。
- 反转段:前 N 个。
- 拼接:段尾接后继。
原理流程
- 递归走到第 N 个,保存后继。
- 段内反转。
- 原段头接后继。
代码 / 示例
ListNode successor = null;
ListNode reverseN(ListNode head, int n) {
if (n == 1) { successor = head.next; return head; }
ListNode newHead = reverseN(head.next, n - 1);
head.next.next = head;
head.next = successor;
return newHead;
}
常见误区
- 误区:未保存后继,反转后段尾断链;正解:基准层记录第 N+1 节点。
- 误区:N 超过链表长度;正解:先校验长度或按实际长度处理。
追问
- Q:头插法迭代怎么写? A:首节点固定为段尾,后续节点逐个插到段头前。
- Q:与整体反转区别? A:保留段后部分不反转,需拼接后继。
02.3.1.1-007 反转链表区间(LC 92)怎么做?
一句话结论
定位区间前驱,用头插法把区间内节点逐个插到前驱之后;O(n) 时间 O(1) 空间;哑节点简化前驱处理。
概念解释
- 前驱:区间左端点的前一节点。
- 头插:区间第二个起逐个插到前驱后。
- 区间外保持不动。
原理流程
- 哑节点出发走到 left 前驱。
- 锚定区间首节点。
- 逐个摘节点插到前驱后。
代码 / 示例
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
for (int i = 0; i < left - 1; i++) pre = pre.next;
ListNode cur = pre.next;
for (int i = 0; i < right - left; i++) {
ListNode next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummy.next;
}
常见误区
- 误区:整体反转再拼接;正解:头插法局部反转更直接。
- 误区:left=1 时无前驱;正解:哑节点统一处理。
追问
- Q:头插法为什么不需要改 pre? A:pre 始终是区间前驱,新节点插在它后面。
- Q:区间长度 1? A:循环不执行,链表不变。
02.3.1.1-008 找链表中间节点(LC 876)怎么做?
一句话结论
快慢指针:slow 一步、fast 两步,fast 到末尾时 slow 即中点;偶数长度返回中间偏右节点;O(n) 时间 O(1) 空间。
概念解释
- 快针两倍速。
- 终止:fast 或 fast.next 为 null。
- 偶数口径:偏右。
原理流程
- slow=fast=head。
- fast 两步,slow 一步。
- fast 不可继续时返回 slow。
代码 / 示例
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
常见误区
- 误区:先求长度再走一半;正解:快慢指针一次扫描。
- 误区:循环条件只判 fast;正解:fast.next 也可能为 null。
追问
- Q:偶数长度要偏左? A:调整初始 fast 或循环条件。
- Q:快慢指针为什么能找中点? A:快针走完全程时慢针恰在半程。
02.3.1.1-009 链表长度怎么求?
一句话结论
遍历计数到 null,O(n) 时间;长度信息常用于倒数定位、环判断与边界校验。
概念解释
- 计数器随遍历累加。
- 空链表长度 0。
- 长度可缓存复用,避免重复遍历。
原理流程
- 计数 0,游标出发。
- 每过一节点加一。
- 到 null 返回计数。
代码 / 示例
int length(ListNode head) {
int len = 0;
for (ListNode cur = head; cur != null; cur = cur.next) len++;
return len;
}
常见误区
- 误区:长度含哑节点;正解:哑节点不计入数据长度。
- 误区:环链表求长度会死循环;正解:有环先判环。
追问
- Q:多次需要长度怎么办? A:结构内维护长度变量,增删时同步更新。
- Q:长度为 0 判空? A:head == null 即空。
02.3.1.1-010 删除给定节点(LC 237)怎么做?
一句话结论
无头节点前驱时,把后继值复制到当前节点,再删除后继;相当于用后继覆盖自身;O(1) 时间,前提不是尾节点。
概念解释
- 无法直接改前驱指针。
- 值覆盖 + 删后继等价删除自身。
- 尾节点无后继,不适用。
原理流程
- 复制 next.val 到当前。
- 当前 next 指向 next.next。
- 后继被摘除。
代码 / 示例
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
常见误区
- 误区:尾节点也这么删;正解:尾节点无后继,需前驱或特殊处理。
- 误区:直接改 node 引用;正解:引用改不动外部指向,必须改节点内容与指针。
追问
- Q:为什么不能把 node 置 null? A:局部引用置空不影响前驱的 next。
- Q:节点含复杂对象? A:复制值语义按题目要求。
02.3.1.1-011 删除倒数第 N 个节点(LC 19)怎么做?
一句话结论
快慢指针:fast 先走 N 步,再同速前进;fast 到尾部时 slow 位于待删节点前驱;哑节点处理删头节点;O(n) 时间 O(1) 空间。
概念解释
- 间距 N:fast 领先 slow N 步。
- slow 定位前驱。
- 哑节点覆盖删头场景。
原理流程
- dummy 接 head。
- fast 先走 N 步。
- 同速到 fast 为 null。
- slow.next 摘除目标。
代码 / 示例
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode slow = dummy, fast = dummy;
for (int i = 0; i < n; i++) fast = fast.next;
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
常见误区
- 误区:先求长度再算正数位置;正解:一次扫描双指针更优。
- 误区:删除头节点时前驱为空;正解:哑节点统一前驱。
追问
- Q:N 等于链表长度? A:删头节点,哑节点下 fast 先走 N 步后 fast 为尾,slow 在 dummy。
- Q:N 越界? A:按题目保证合法,否则先校验长度。
02.3.1.1-012 奇偶链表(LC 328)怎么做?
一句话结论
两个头部分别串接奇数位与偶数位,遍历完把偶链表接到奇链表尾部;O(n) 时间 O(1) 空间,保持相对顺序。
概念解释
- 奇偶按位置,不按值。
- 两条子链分别拼接。
- 尾部互连。
原理流程
- 奇头、偶头分离。
- 交替摘节点到对应链。
- 奇链尾接偶链头。
代码 / 示例
public ListNode oddEvenList(ListNode head) {
if (head == null) return null;
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
常见误区
- 误区:按节点值奇偶分组;正解:按位置奇偶。
- 误区:遍历中断链;正解:每步先保存后继再改指针。
追问
- Q:长度 1/2? A:偶链为空或单节点,直接互连。
- Q:空间 O(n) 做法? A:两趟收集再拼接,不如原地指针。
02.3.1.1-013 回文链表(LC 234)怎么做?
一句话结论
快慢指针找中点,反转后半段,逐段比较;可再还原链表;O(n) 时间 O(1) 空间。
概念解释
- 中点分割前后半。
- 后半反转便于前向比较。
- 比较后可恢复结构。
原理流程
- 快慢找中点。
- 反转后半。
- 双指针比较两段。
代码 / 示例
public boolean isPalindrome(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode second = reverse(slow);
ListNode p = head, q = second;
while (q != null) {
if (p.val != q.val) return false;
p = p.next; q = q.next;
}
return true;
}
ListNode reverse(ListNode h) {
ListNode prev = null;
while (h != null) {
ListNode n = h.next; h.next = prev; prev = h; h = n;
}
return prev;
}
常见误区
- 误区:复制到数组再双指针;正解:反转后半 O(1) 额外空间。
- 误区:奇数长度中点归属判断错;正解:后半从 slow 开始,比较按后半长度。
追问
- Q:需要还原链表吗? A:题目无要求可不动;工程上可再反转接回。
- Q:递归做法空间? A:O(n) 栈空间。
02.3.1.1-014 两数相加(LC 2)怎么做?
一句话结论
按位遍历两链表,维护进位,逐位生成结果节点;短链按 0 处理;最高位进位补节点;O(max(m,n)) 时间 O(1) 额外(结果除外)。
概念解释
- 低位在前,正好逐位相加。
- 进位带到下一位。
- 结果新建节点。
原理流程
- 哑节点接结果链。
- 双指针逐位加和加进位。
- 生成个位节点,更新进位。
- 收尾进位补节点。
代码 / 示例
public ListNode addTwoNumbers(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), tail = dummy;
int carry = 0;
while (a != null || b != null || carry != 0) {
int x = a != null ? a.val : 0;
int y = b != null ? b.val : 0;
int sum = x + y + carry;
tail.next = new ListNode(sum % 10);
carry = sum / 10;
tail = tail.next;
if (a != null) a = a.next;
if (b != null) b = b.next;
}
return dummy.next;
}
常见误区
- 误区:长短不一直接停止;正解:短链按 0 继续处理高位。
- 误区:最高位进位遗漏;正解:循环条件带 carry。
追问
- Q:链表高位在前怎么办? A:先反转或用栈存低位。
- Q:结果长度多少? A:不超过 max(m,n)+1。
02.3.1.1-015 复制带随机指针链表(LC 138)思路是什么?
一句话结论
哈希表存原节点 → 复制节点映射,先复制所有节点再连 next 与 random;O(n) 时间 O(n) 空间;进阶可原地交织拆分,O(1) 额外空间。
概念解释
- random 指向任意节点。
- 映射表保证复制节点对应正确。
- 两遍:建节点、连指针。
原理流程
- 遍历建复制节点并存映射。
- 按映射连 next、random。
- 返回复制头。
代码 / 图示
原节点 A → 复制 A'
map: A → A'
第二遍:A'.next = map[A.next]
常见误区
- 误区:第一遍就连 random;正解:被指节点可能尚未复制。
- 误区:原地交织忘记拆分;正解:复制节点插原节点后,再分离两链。
追问
- Q:原地交织怎么做? A:原节点后插复制节点,复制 random 指向原 random 的后继,最后拆分。
- Q:random 可为 null? A:映射与连接都判空。
02.3.1.1-016 链表插入删除要注意哪些指针细节?
一句话结论
插入先连新节点后继再接前驱;删除先存后继再摘节点;所有改指针操作防断链,头节点变动用哑节点统一。
概念解释
- 顺序:新链先于旧链。
- 防断:改前驱前存后继。
- 头处理:哑节点覆盖。
原理流程
- 定位前驱。
- 插入:新节点.next=前驱.next,前驱.next=新节点。
- 删除:前驱.next=待删.next。
代码 / 图示
插入:n.next = p.next; p.next = n;
删除:p.next = x.next;
常见误区
- 误区:先改前驱再连新节点后继;正解:先接新节点后继,避免丢失原后继。
- 误区:删除节点未被引用回收;正解:Java 由 GC 处理,断开引用即可。
追问
- Q:在节点后插入? A:无需前驱,直接操作该节点后继。
- Q:链表有序插入? A:先遍历定位插入点,再按顺序连指针。
02.3.1.1-017 哑节点(哨兵)解决什么问题?
一句话结论
哑节点挂在头节点前,使头节点与其他节点操作口径一致,免去删除/插入头节点的特判;返回 dummy.next。
概念解释
- 哨兵:不存数据的前置节点。
- 统一前驱:任何节点都有前驱。
- 简化边界分支。
原理流程
- dummy.next = head。
- 游标从 dummy 开始操作。
- 返回 dummy.next。
代码 / 示例
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
// 操作 cur.next
return dummy.next;
常见误区
- 误区:返回 dummy;正解:dummy.next 才是链表头。
- 误区:认为空链表不需要哑节点;正解:可以统一建哑节点,dummy.next 为 null,口径一致。
追问
- Q:哑节点占空间吗? A:常数一个节点,O(1)。
- Q:哪些题必用哑节点? A:可能删头节点、合并链表等。
02.3.1.1-018 链表递归的空间复杂度怎么算?
一句话结论
递归空间为调用栈深度,线性递归深度 n 即 O(n);迭代版只用指针变量 O(1);长链表优先迭代避免栈溢出。
概念解释
- 栈帧:每层递归保存返回位置与局部变量。
- 深度:最长递归路径。
- 迭代:无调用栈。
原理流程
- 估算递归深度。
- 每层栈帧常数空间。
- 深度 × 单层空间。
代码 / 图示
反转递归:深度 n → 栈 O(n)
反转迭代:三指针 → O(1)
常见误区
- 误区:递归只看节点数不看深度;正解:栈空间按深度。
- 误区:尾递归在 Java 被优化;正解:JVM 不保证尾调用消除。
追问
- Q:链表过长递归溢出怎么办? A:改迭代或显式栈。
- Q:递归优点是什么? A:代码简洁,适合分治结构。
02.3.1.1-019 链表题有哪些边界用例?
一句话结论
空链表、单节点、两节点、头节点被删/被反转、尾节点、环(另章)、值重复;先覆盖这些再测正常多节点。
概念解释
- 空与最短:验证初始与返回。
- 头变动:验证哑节点。
- 尾部:next 为 null 判断。
原理流程
- 入口判空。
- 构造 1/2 节点用例。
- 检查头与尾指针。
代码 / 图示
null / [x] / [x,y]
删除头 / 反转整链
尾节点 next=null
重复值节点
常见误区
- 误区:默认链表非空;正解:函数入口先判 head。
- 误区:两节点指针操作遗漏;正解:小规模用例最易暴露断链。
追问
- Q:空链表返回什么? A:null 或 false,按题目口径。
- Q:单节点反转结果? A:原节点本身。
02.3.1.1-020 链表题复杂度怎么汇报?
一句话结论
遍历/反转/删除已知节点多为 O(n) 时间 O(1) 额外空间;递归版加 O(n) 栈空间;查找第 i 位 O(i);汇报区分遍历与查找。
概念解释
- 时间:扫描轮次。
- 空间:指针/栈/映射表。
- 已知节点删除与按位删除不同。
原理流程
- 统计遍历次数。
- 标注辅助结构。
- 递归栈单列。
代码 / 图示
迭代反转:O(n) 时间 / O(1) 空间
递归反转:O(n) 时间 / O(n) 栈
按位删除:O(n) 时间 / O(1) 空间
常见误区
- 误区:链表操作都是 O(1);正解:定位前驱通常 O(n)。
- 误区:映射表方案不报空间;正解:复制随机指针 O(n) 空间。
追问
- Q:链表随机访问复杂度? A:O(n)。
- Q:合并两条链表复杂度? A:O(m+n),见合并章节。