链表：指针操作的基本功

这一课你将能做到

1. 画出链表节点的指向关系，用「断链前先保存」的原则完成反转
2. 用快慢指针判断环并说出环入口的求法
3. 用哑节点（dummy）合并两个有序链表，理解它为什么能消掉分支

为什么要学

数组在内存里是一排连续座位，链表则是一串「各带地址条的节点」——每个节点存数据和下一个节点的引用，节点散落内存也没关系。插入、删除不需要搬动整排元素，O(1) 就能改指针完成。

链表在后端开发中直接写得不算多（各种容器类已经封装好），但 LRU 缓存（LinkedHashMap / 自定义双向链表）、跳表、消息队列的底层结构都离不开它。面试更现实的意义是：链表题是「指针纪律」的试金石——谁在断链前保存了后续节点、谁考虑了空指针，一眼可见。而且反转、判环、合并这三题几乎是必考清单，属于必须形成肌肉记忆的内容。

先建立图像

单链表节点定义（所有题目的公共前提）：

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

链表：   1 → 2 → 3 → null
反转后： 3 → 2 → 1 → null

判环：   3 → 4 → 5
         ↑       ↓
         7 ← 6 ←      ← fast 走两步、slow 走一步，必相遇

链表题三大纪律：

1. 断链前先存：改 next 指向前，先把原后继保存好，否则后半截链表直接丢失。
2. 凡是 x.next 必先确认 x 非 null。
3. 头节点可能变化时，用 dummy 占位，避免单独处理头节点的分支。

跟着做

步骤 1：LeetCode 206「反转链表」（简单）

给定单链表头节点，反转整条链并返回新头节点。

迭代思路用三个指针：prev（已反转部分的头）、curr（当前处理节点）、next（暂存原后继）。每个节点做同一个动作——把 next 指针从「指向后」改成「指向前」。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next; // 1. 先存原后继（断链前先存）
            curr.next = prev;          // 2. 反转指向
            prev = curr;               // 3. prev 前进一步
            curr = next;               // 4. curr 前进一步
        }
        return prev; // curr 已为 null，prev 就是新头
    }
}

逐点讲：循环不变量——prev 是「已经反转好部分」的头，curr 是「尚未反转部分」的头。时间 O(n)，空间 O(1)。

递归写法（面试也常考推导）：

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next); // 反转子链
        head.next.next = head; // 子链原尾（head.next）反过来指向自己
        head.next = null;      // 自己成为新尾，断开旧方向
        return newHead;
    }
}

递归时间 O(n)、空间 O(n)（调用栈）。建议先吃透迭代，递归用来展示理解深度。