链表与反转

什么是链表

链表（linked list）是一种由节点串起来的线性结构。每个节点存两样东西：

• 一个值
• 一个指向下一个节点的指针（next）

跟数组不同，链表节点在内存里不需要连续 —— 它们靠指针手拉手。代价是：不能 O(1) 随机访问（要从头一个个跳）；好处是：插入/删除 O(1)（只需改两根指针）。

struct Node {
  int val;
  Node* next;
};

链表末尾的节点 next 指向 nullptr（图里画成虚线指向 “null”）。

反转：指针重连的经典

链表反转几乎是所有链表面试题的入门必练。原地反转的核心是三个指针：prev、cur、nxt，按下面四步循环：

1. 用 nxt 把当前节点的下一个节点先保存下来（不然下一步重连后就找不到了）
2. 把 cur 的箭头反转指向 prev
3. prev 前进到 cur
4. cur 前进到 nxt

当 cur 走到 nullptr，整条链表反转完成，新的头就是 prev。

为什么要先保存 nxt

第 2 步执行 cur.next = prev 之后，原来的 cur.next 就丢了。如果不先用 nxt 备份，下次循环就没法继续往后走。

可视化里你能看到：

• 暖红色 prev：已经反转过的部分的头
• 深蓝 cur：当前正在被反转的节点
• 灰色 nxt：临时保存的下一个节点
• 反转后的箭头会画成蓝色弧线绕到节点下方，避免和未反转的灰色箭头重叠

复杂度

• 时间：O(n) — 每个节点只访问一次
• 空间：O(1) — 只用三个指针变量