链表、队列与栈

链表没有数组下标,没有一个能信得过的 length 字段,也没有任何安全网——一个指针没管好,你要么把半条链表丢在地上,要么把它系成一个死循环。这种脆弱正是它成为面试常客的原因:一道链表题本质上是一场穿着数据结构外衣的指针纪律考试。这一课我们从一个原语——指针翻转——搭起整套工具箱,然后展示翻转、快慢指针、dummy head、拆分再重组这几件事如何覆盖几乎所有会被塞到你手里的链表题,从温柔的 LC 206 一路到按 k 个一组翻转。

链表不是数组

先从字节住在哪里说起。数组是堆上一整块连续内存,所以取第 i 个元素只要一次乘加——O(1) 随机访问。链表是散落在堆上任意角落的一堆节点,只靠 next 引用串起来,所以要够到第 i 个节点就得走 i 跳——O(n) 访问。你用快速查找换来了廉价的拼接:在链表中间插入或删除只是几次指针交换,不用搬动任何元素。

这节课花了实打实的时间讲一个在 Java 里最容易绊倒人的区别:null 引用不是空容器。下面是四种不同的状态:

• int[] arr = null——堆上根本没有数组对象,引用什么都没指向。
• int[] arr = new int[0]——堆上有一个真实的数组对象,只是容量为零。
• ArrayList<Integer> ls = null——没有 list 对象,一解引用立刻抛异常。
• ArrayList<Integer> ls = new ArrayList<>()——真实对象,size == 0,但底层容量不为零(首次插入时默认是 10)。

当成一条规则记住:null 意思是「这个引用在堆里没有对象」;size == 0 意思是「有对象,只是还没有有效值」。每道链表题一开始都要判断你的输入可能是这两者中的哪一个——这才是 head == null 那个 guard 真正在测的东西。

节点、dummy 与那几个 corner case

节点本身平平无奇,而这正是重点——一个树节点就是同一个对象、把一个 next 换成两个孩子指针,所以同一套翻转肌肉后面能直接迁移到树上。Java 标准库用同一种节点类型同时支撑单链表和双链表;单链表情形里 pre 指针闲置不用而已。

class ListNode {
    int val;
    ListNode next;
    ListNode pre;              // 同一种节点类型,单链表与双链表通用
    ListNode(int val) {
        this.val = val;
        this.next = null;
        this.pre  = null;
    }
}

// 树就是同一个想法——把 next 换成 left/right
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

两个习惯能让链表代码不崩。第一,corner case 永远是同样两个:head == null(空链表)和 head.next == null(只有一个节点)。九成的链表函数开头都是 if (head == null || head.next == null) return head;。第二,主体几乎总是一个 while 循环,而唯一有意思的设计决策是循环退出时 cur 停在哪——先把这个定了,后处理自己就写出来了。

再说说 dummy 节点。ListNode dummy = new ListNode(0) 是粘在头前面的一个假节点,让「插到 head 之前」不再是特例。它确实好用——merge、partition、insertion sort 都靠它——但老师的批注值得复述:万不得已才用。有些面试官会把「张口就来 dummy」解读成「搞不定会动的 head」,所以只要题目允许,就直接操作真实 head,只在链表头真正不稳定的时候才掏出 dummy。

翻转:母题(LC 206)

这一课如果只带走一样东西,就带这个。LC 206 Reverse Linked List 是另外半数题目搭建其上的那个原子。迭代版沿着链表走三个指针,一路把每个 next 翻过来:

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode pre = null;   // cur 后面已经反转好的部分
    ListNode cur = head;   // 当前正在翻的节点
    ListNode next = null;  // 先存好,免得丢掉后面
    while (cur != null) {
        next = cur.next;   // 1. 先把前路存下来
        cur.next = pre;    // 2. 把箭头翻向后
        pre = cur;         // 3. 推进已反转的前沿
        cur = next;        // 4. 往前走一步
    }
    return pre;            // cur 到 null;pre 就是新 head
}

循环在 cur 走到 null 时退出,此刻 pre 正停在最后访问的节点上——新的 head。注意 next 存在的唯一目的就是遵守第 (1) 条:你一写下 cur.next = pre 就把前向链接毁了,所以必须提前一行把它存好,否则链表后半段就没了。

递归版自顶向下说的是同一件事。「以 1 为头的链表反转后是什么?我不知道——先反转以 2 为头的链表,再把 1 挂到它尾巴上。」递归在最后一个节点触底(那就是反转后的结果),然后往回走的路上每一层做两个赋值:

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;  // base case = 反转后的结果
    ListNode newHead = reverseList(head.next);  // 反转 head 之后的全部
    // --- 墙:这行以下,后半段已经反转好了 ---
    head.next.next = head;   // head 后面那个节点现在回指 head
    head.next = null;      // head 变成新尾巴,给它补 null
    return newHead;          // 同一个 newHead 一路冒泡返回
}

有一个诱人的错误写法值得点名,因为候选人一遍遍地写它:先翻指针再递归(head.next.next = head; head.next = null; return reverseList(next))。它失败的原因很微妙——你一旦把 head.next 置空,就切断了通往刚反转好的头节点的唯一路径,各层再也接不回去,于是返回了错误的节点。规则是:翻转要先递归,回来的路上再改指针。迭代 O(1) 空间,是安全默认值;递归更漂亮,但要付 O(n) 调用栈,链表很长时会把栈撑爆。

翻转变体:成对、k 组、按区间

LC 206 一旦成了肌肉记忆,三道「更难」的题不过是给「一次翻多少」装了个调速器。

LC 24 Swap Nodes in Pairs 按两个一组翻:1→2→3→4 变成 2→1→4→3。递归形状就是 LC 206,只是递归往前跳两个节点(reverse(head.next.next)),翻转当前这对,返回这对的新头。LC 92 Reverse Linked List II 只翻 m 到 n 之间的子链表。这才是 dummy 的正当用途:把 pre 停在位置 m 的前一格,然后反复把 start 后面的节点摘下来、头插到反转窗口的最前面——n − m 次头插就完事,反转碰到真实 head 时也不用特判。

LC 25 Reverse Nodes in k-Group 是皇冠上的明珠,也是一道「现场写对就很秀」的题。先走 k 个节点确认凑得齐一整组(凑不齐的话尾部原样不动——这是题目要求)。对剩下的部分递归拿到下游所有节点的新头,再把这组 k 个反转、拼上去:

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || head.next == null || k < 2) return head;

    int i = k;
    ListNode tmp = head;
    while (i > 0 && tmp != null) {   // 探测:凑得齐一整组 k 吗?
        tmp = tmp.next;
        i--;
    }
    if (i == 0) {                     // 凑齐了——tmp 是剩余部分的头
        ListNode newHead = reverseKGroup(tmp, k);  // 先把剩下的解决掉
        i = k;
        ListNode next = null;
        while (i > 0) {              // 把这一组翻转,接到 newHead 上
            next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
            i--;
        }
        head = newHead;
    }
    return head;                     // 凑不齐的末尾一组原样保留
}

优雅之处在于:整个家族——单个节点、成对、k 组——是同一个翻转循环换了个步长,而 base/corner case(head == null、head.next == null)从头到尾不变。

快慢指针:中点与倒数第 k 个

第二个大想法,是在一趟里用两个不同速度的指针往下走。找中点(LC 876) 是经典用法:slow 一次一跳,fast 一次两跳,当 fast 掉出末尾时,slow 就在中点。全部胜负手在循环条件上,因为它决定了偶数长度时「中点」指的是哪个节点。用 fast.next != null && fast.next.next != null,slow 落在偏左的中点上——这正是拆分前想要的,前半段多留一个节点。

ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
    slow = slow.next;         // 每轮 +1
    fast = fast.next.next;    // 每轮 +2
}
// slow 是(偏左的)中点;slow.next 是后半段的起点

倒数第 k 个节点(LintCode 经典题,也是 LC 19 Remove Nth Node From End 的引擎)用的是固定间距而不是速度差:先让 fast 往前走 k 步——每步都检查 fast != null,这样 k 太大时返回 null 而不是抛异常——再让 slow 和 fast 一起走。fast 到末尾时,slow 恰好离尾巴 k 个。一趟走完,不用先算长度。

环:检测、长度,与 a = c 技巧

「环」不一定是一个完整的圆圈——它是任何一个 next 重新指回链表某处的节点,形状像个套索。判断有没有重复节点有三招:一个 hash set 记录访问过的节点(O(n) 空间),一个 visited 布尔字段(如果允许你改节点),或者——面试官想要的那个——O(1) 空间的快慢指针。只要 fast 套了 slow 一圈,就有环(LC 141);如果 fast 跑到 null,就没有。

相遇点还能推出两个后续。环的长度:相遇之后,冻住一个指针,让另一个带着计数器绕一圈直到回到原地。环的入口(LC 142):这才是漂亮的地方。设 a 是头到环入口的距离、b 是入口到相遇点的距离、c 是环剩下的部分。slow 走了 a + b;fast 走了它的两倍还多绕了一圈,于是 2(a + b) = a + 2b + c,化简得 a = c。翻译过来:头到入口的距离,等于相遇点绕回入口的距离。所以把一个指针重置回 head,两个指针每次各走一步,它们恰好在入口相撞。

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {          // 在环内相遇
            fast = head;             // a = c,把一个重置回 head
            while (slow != fast) {    // 一起同步走
                slow = slow.next;
                fast = fast.next;
            }
            return slow;             // 相撞处 == 入口
        }
    }
    return null;                    // fast 掉出去了 → 无环
}

同样这种「双指针恒等式」的味道也驱动着 LC 160 Intersection of Two Linked Lists:让指针 a 走完链表 A 再续着走链表 B,b 走完 B 再续着走 A。两者总共都走 lenA + lenB,于是它们会同时到达那个共享节点——或者两条链表永不相交时,同时到达 null。面试官会追问的那个细节:循环必须判 a == null,不是 a.next == null。不相交那种情况以 a == b == null 结束;如果你跳过了 null 这个状态,就会漏掉这个终止,要么死循环要么解引用 null。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;   // 判 null,不是 a.next:保住 null 这个状态
        b = (b == null) ? headA : b.next;
    }
    return a;   // 共享节点,不相交则为 null
}

删除与 CRUD 思维

老师把每种数据结构都框成 CRUD——增、查、改、删——甚至类比到 REST API(资源用 URL 寻址、操作用 HTTP verb 命名),就是想说「这个东西支持哪些操作?」是一份值得对任何结构过一遍的清单。对链表来说,删除分成两种形状。

能拿到前驱节点的删除是简单情形:pre.next = pre.next.next,目标就被摘掉了。只握着节点本身的删除(LC 237)是脑筋急转弯——你回不到前面去,于是把后继的值拷进当前节点,转而摘掉后继:node.val = node.next.val; node.next = node.next.next。你并没有删掉「这个」节点,而是冒充了下一个、把它删了。

• LC 203 Remove Linked List Elements——删掉所有等于 val 的节点。先跳过开头匹配的一段(while (head != null && head.val == val) head = head.next),再跑一个 cur.next.val == val ? 摘掉 : 前进 的循环。也有两行的递归版,但笔记里诚实地标注了:这里递归太深、长链表有栈溢出风险——优先用迭代。
• LC 83 Remove Duplicates from Sorted List——因为相等的值相邻,只要 cur.val == cur.next.val 就一直往前摘副本,否则前进一格。和 LC 203 同一副骨架,换了个匹配条件。
• LC 237 Delete Node in a Linked List——上面那个「拷值前顶」技巧,O(1),只在该节点不是尾节点时才成立。

合并与排序

LC 21 Merge Two Sorted Lists 是这一节其余一切背后的主力。两条链表一起走,总是把较小的头拼到 dummy 锚定的 tail 上,最后把剩下的整段挂上去:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    ListNode dummy = new ListNode(0), tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; }
        else                 { tail.next = l2; l2 = l2.next; }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;   // 剩下的整段一次性挂上
    return dummy.next;
}

还有一个干净的递归孪生版——if (l1.val < l2.val) { l1.next = merge(l1.next, l2); return l1; } 对称处理另一支——它带着一个好记的道理:递归的 base case 恰好就是迭代的 corner case(l1 == null、l2 == null)。你能枚举出一个,就能写出另一个。

LC 147 Insertion Sort List 于是就是「不断 call insert」:在一个 dummy 后面维护一条有序链表,对每个新来的节点,走一遍有序部分找到它的位置插进去——O(n²),稳定,唯一的细节是插入之前先把 cur.next 存好,因为 insert 会改 cur.next,否则你就丢了在输入链表里的位置。

LC 148 Sort List 要求 O(n log n) 且常数额外空间,「链表上的 n log n」应当立刻让你想到 merge sort(quicksort 依赖随机访问,不合适)。用快慢指针把链表切两半——这里有个人人都踩的坑:递归之前必须用 prev.next = null 把前半段断开,否则两半仍然彼此指着。分别递归排序两半,再复用 LC 21 的 merge。就是三个你已经会的原语拼在一起。

拆分再重组

一整个家族的题都归约成「按某个规则把链表拆成两条,再织回去」。模板完全一样,只有拆分的判定条件在变。

LC 143 Reorder List(1 2 3 … n → 1 n 2 (n-1) …)是模块化思维的招牌。朴素做法把整条链表反转再交叉,但原地 O(1) 空间的解法就是三个你已经写过的子过程:找中点、反转后半段、把两半交替合并。用 mid.next = null 把两半切开,剩下的就是组合。

LC 328 Odd Even Linked List 按位置织:一趟里穿起一条 odd 链和一条 even 链,再把 even 头挂到 odd 尾上。LC 86 Partition List 按值织:把 < x 的节点送进「小」链、其余送进「大」链,再拼接。这一道藏着最常见的那个链表 bug——拼接前必须 larger.next = null,否则大链的尾巴仍然引用着一个已经迁进小链的节点,你就造出了一个环。和 Sort List 里忘写 prev.next = null、Reorder 里忘写 mid.next = null 是同一种病:凡拆分,必补 null。

链表上的算术

链表兼职大整数——一位数字一个节点——这正是为什么当一个数会溢出 int 或 long 时,面试官会拿它出题。LC 2 Add Two Numbers 把数字按低位在前存,于是从左到右带着一个 carry 相加,每步产出一个输出节点;循环条件 l1 != null || l2 != null || carry != 0 优雅地把最后的进位(999 + 1 那种)也一并折进去,不用单独分支。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), head = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {   // carry 也能让循环续命
        int v1 = (l1 == null) ? 0 : l1.val;
        int v2 = (l2 == null) ? 0 : l2.val;
        int sum = carry + v1 + v2;
        head.next = new ListNode(sum % 10);
        carry = sum / 10;
        head = head.next;
        l1 = (l1 == null) ? null : l1.next;
        l2 = (l2 == null) ? null : l2.next;
    }
    return dummy.next;
}

LC 369 Plus One Linked List 是高位在前的变体。因为你只能往前走,干净的做法是反转、加一带进位、再反转回去——或者不反转,找到最右边那个不是 9 的数字,把它加一,再把它后面的全置零(如果整条都是 9,就在最前面挂一个新的 1 节点)。两者都是换了坐标系的进位机制,也都强过硬做字符串算术——那玩意儿会淹死在空串、前导零之类的边界里。

刷题清单