罗罗编程学习记录
本页内容 展开查看

02.3.1.1 单链表基础操作与反转

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.1 链表

02.3.1.1-001 链表与数组有什么区别?

一句话结论

链表节点离散存储、靠指针串联,插入删除 O(1)(已知节点),随机访问 O(n);数组连续存储、随机访问 O(1),中间增删 O(n)。

概念解释

  • 链表:无连续地址,指针跳转。
  • 数组:连续内存,下标寻址。
  • 选型看主要操作是访问还是增删。

原理流程

  1. 列出高频操作:查、插、删、遍历。
  2. 对照两结构代价。
  3. 按约束选择。

代码 / 图示

链表: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。

原理流程

  1. 定义节点结构。
  2. 头指针定位链表。
  3. 末尾以 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。
  • 头指针保留:结果返回与入口使用。

原理流程

  1. cur = head。
  2. cur 非空处理,cur = cur.next。
  3. 到 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 最终是新头。

原理流程

  1. prev=null,cur=head。
  2. 存 next,cur.next=prev,prev=cur,cur=next。
  3. 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 接到后继段末尾。
  • 基准:空或单节点直接返回。

原理流程

  1. 基准 head 为空/单节点返回。
  2. 递归反转后继得 newHead。
  3. 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 个。
  • 拼接:段尾接后继。

原理流程

  1. 递归走到第 N 个,保存后继。
  2. 段内反转。
  3. 原段头接后继。

代码 / 示例

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) 空间;哑节点简化前驱处理。

概念解释

  • 前驱:区间左端点的前一节点。
  • 头插:区间第二个起逐个插到前驱后。
  • 区间外保持不动。

原理流程

  1. 哑节点出发走到 left 前驱。
  2. 锚定区间首节点。
  3. 逐个摘节点插到前驱后。

代码 / 示例

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。
  • 偶数口径:偏右。

原理流程

  1. slow=fast=head。
  2. fast 两步,slow 一步。
  3. 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。
  • 长度可缓存复用,避免重复遍历。

原理流程

  1. 计数 0,游标出发。
  2. 每过一节点加一。
  3. 到 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) 时间,前提不是尾节点。

概念解释

  • 无法直接改前驱指针。
  • 值覆盖 + 删后继等价删除自身。
  • 尾节点无后继,不适用。

原理流程

  1. 复制 next.val 到当前。
  2. 当前 next 指向 next.next。
  3. 后继被摘除。

代码 / 示例

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 定位前驱。
  • 哑节点覆盖删头场景。

原理流程

  1. dummy 接 head。
  2. fast 先走 N 步。
  3. 同速到 fast 为 null。
  4. 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) 空间,保持相对顺序。

概念解释

  • 奇偶按位置,不按值。
  • 两条子链分别拼接。
  • 尾部互连。

原理流程

  1. 奇头、偶头分离。
  2. 交替摘节点到对应链。
  3. 奇链尾接偶链头。

代码 / 示例

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) 空间。

概念解释

  • 中点分割前后半。
  • 后半反转便于前向比较。
  • 比较后可恢复结构。

原理流程

  1. 快慢找中点。
  2. 反转后半。
  3. 双指针比较两段。

代码 / 示例

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) 额外(结果除外)。

概念解释

  • 低位在前,正好逐位相加。
  • 进位带到下一位。
  • 结果新建节点。

原理流程

  1. 哑节点接结果链。
  2. 双指针逐位加和加进位。
  3. 生成个位节点,更新进位。
  4. 收尾进位补节点。

代码 / 示例

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 指向任意节点。
  • 映射表保证复制节点对应正确。
  • 两遍:建节点、连指针。

原理流程

  1. 遍历建复制节点并存映射。
  2. 按映射连 next、random。
  3. 返回复制头。

代码 / 图示

原节点 A → 复制 A'
map: A → A'
第二遍:A'.next = map[A.next]

常见误区

  • 误区:第一遍就连 random;正解:被指节点可能尚未复制。
  • 误区:原地交织忘记拆分;正解:复制节点插原节点后,再分离两链。

追问

  • Q:原地交织怎么做? A:原节点后插复制节点,复制 random 指向原 random 的后继,最后拆分。
  • Q:random 可为 null? A:映射与连接都判空。

02.3.1.1-016 链表插入删除要注意哪些指针细节?

一句话结论

插入先连新节点后继再接前驱;删除先存后继再摘节点;所有改指针操作防断链,头节点变动用哑节点统一。

概念解释

  • 顺序:新链先于旧链。
  • 防断:改前驱前存后继。
  • 头处理:哑节点覆盖。

原理流程

  1. 定位前驱。
  2. 插入:新节点.next=前驱.next,前驱.next=新节点。
  3. 删除:前驱.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。

概念解释

  • 哨兵:不存数据的前置节点。
  • 统一前驱:任何节点都有前驱。
  • 简化边界分支。

原理流程

  1. dummy.next = head。
  2. 游标从 dummy 开始操作。
  3. 返回 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);长链表优先迭代避免栈溢出。

概念解释

  • 栈帧:每层递归保存返回位置与局部变量。
  • 深度:最长递归路径。
  • 迭代:无调用栈。

原理流程

  1. 估算递归深度。
  2. 每层栈帧常数空间。
  3. 深度 × 单层空间。

代码 / 图示

反转递归:深度 n → 栈 O(n)
反转迭代:三指针 → O(1)

常见误区

  • 误区:递归只看节点数不看深度;正解:栈空间按深度。
  • 误区:尾递归在 Java 被优化;正解:JVM 不保证尾调用消除。

追问

  • Q:链表过长递归溢出怎么办? A:改迭代或显式栈。
  • Q:递归优点是什么? A:代码简洁,适合分治结构。

02.3.1.1-019 链表题有哪些边界用例?

一句话结论

空链表、单节点、两节点、头节点被删/被反转、尾节点、环(另章)、值重复;先覆盖这些再测正常多节点。

概念解释

  • 空与最短:验证初始与返回。
  • 头变动:验证哑节点。
  • 尾部:next 为 null 判断。

原理流程

  1. 入口判空。
  2. 构造 1/2 节点用例。
  3. 检查头与尾指针。

代码 / 图示

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);汇报区分遍历与查找。

概念解释

  • 时间:扫描轮次。
  • 空间:指针/栈/映射表。
  • 已知节点删除与按位删除不同。

原理流程

  1. 统计遍历次数。
  2. 标注辅助结构。
  3. 递归栈单列。

代码 / 图示

迭代反转: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),见合并章节。