链表为什么有时要维护尾指针？尾指针能把哪些操作优化到 O(1)？

简化版

单链表只保存头指针时，尾部追加通常要从头遍历到尾，时间是 O(n)。如果额外维护尾指针 tail，就能把尾插优化到 O(1)，常用于队列、日志追加、链表拼接等场景。

详细版

尾指针指向链表最后一个节点。它本质上是用额外状态换取尾部操作效率。

典型收益：

尾插：没有 tail 要遍历找尾，有 tail 可以 tail.next = node; tail = node。
队列入队：队尾追加 O(1)，配合头指针出队 O(1)。
链表拼接：如果知道 A 的尾，可以直接把 A.tail.next = B.head。
构造新链表：遍历旧链表时不断尾插，比每次找尾稳定得多。

但尾指针也有维护成本：删除尾节点时，单链表无法通过 tail 直接找到前驱，仍可能需要 O(n)。所以尾指针优化的是“尾部追加”和“接链”，不等于所有尾部操作都是 O(1)。

完整版教学

一、头指针和尾指针分别解决什么问题

链表的头指针让你能找到整条链的入口。没有头指针，链表就像没有门牌号的一串房间，无法开始遍历。

尾指针解决的是另一个问题：快速找到最后一个节点。只保存头指针时，尾节点没有直接入口，你必须从头一路走到 next == null 的节点。

只有 head：
head -> 1 -> 2 -> 3 -> null
想尾插 4，需要先走到 3

head + tail：
head -> 1 -> 2 -> 3 -> null
                ^
               tail

所以尾指针不是链表必需品，而是性能缓存。它缓存了“最后一个节点是谁”这个信息，让某些操作不再重复扫描。

二、尾插为什么能从 O(n) 变成 O(1)

假设链表长度是 10000，没有尾指针时追加一个节点，要检查 10000 个左右的 next 才能找到尾。追加 1000 次，最坏会接近 10000 + 10001 + … 的级别。

有尾指针时，每次追加只做常数次操作：

tail.next = newNode;
tail = newNode;

如果链表原本为空，还需要同时设置 head 和 tail：

if (!head) {
  head = tail = newNode;
} else {
  tail.next = newNode;
  tail = newNode;
}

这就是队列常用链表加尾指针的原因。入队走尾部，出队走头部，两端都能 O(1)。

三、尾指针不是万能的

很多同学听到 tail 就以为“尾部操作都是 O(1)”。这在单链表里不成立。删除尾节点时，你需要把倒数第二个节点的 next 置空，并把 tail 更新成倒数第二个节点。

问题是：单链表节点只知道下一个节点，不知道前一个节点。

1 -> 2 -> 3 -> null
          ^
         tail

要删除 3，必须找到 2

所以单链表有尾指针时，尾插是 O(1)，删尾仍通常是 O(n)。如果需要频繁删尾，就要考虑双向链表，因为双向链表的尾节点能通过 prev 找到前驱。

四、链表拼接时尾指针的价值

尾指针在“拼接两条链”时很有用。假设 A 是 1 -> 2 -> 3，B 是 4 -> 5。如果 A 有 tail，拼接只需要：

A.tail.next = B.head
A.tail = B.tail

对比表：

场景	无尾指针	有尾指针
追加单个节点	先遍历找尾，O(n)	直接接到尾，O(1)
拼接另一条链	先找 A 的尾，O(n)	直接接 B，O(1)
删除尾节点	仍要找前驱，O(n)	单链表仍是 O(n)
查看头节点	O(1)	O(1)

注意拼接后要更新尾指针。如果只接了 A.tail.next = B.head，但忘记 A.tail = B.tail，下一次尾插会接在旧尾后面，可能破坏链表。

五、空链表和单节点链表怎么维护

尾指针最容易错在空链表边界。空链表时 head = null, tail = null。插入第一个节点后，头尾都应该指向同一个节点。

删除唯一节点后，也必须同时清空头尾：

// 删除唯一节点
head = null;
tail = null;

如果只改 head = null，但 tail 还指向旧节点，后续尾插会把新节点接到一个已经不属于链表的旧节点后面。这个 bug 隐蔽但很危险，因为遍历 head 看不到旧尾，状态却已经坏了。

六、适用场景和代价如何权衡

尾指针适合尾部追加频繁的场景，例如链表队列、构造结果链表、日志缓冲、邻接表追加边。它的额外空间只是一个指针，通常可以忽略。

但它带来状态一致性要求：每次改变尾部、清空链表、拼接链表，都要同步更新 tail。对于只做头插、头删的小链表，尾指针可能没有必要。

记忆钩子：tail 是“最后一个节点是谁”的缓存，能救尾插和拼接，救不了单链表删尾。

七、常见误区与追问

误区：有尾指针后删除尾节点也是 O(1)。 单链表找不到尾节点前驱，删尾仍要从头找倒数第二个节点。
误区：空链表插入时只更新 head。 第一个节点既是头也是尾，必须 head、tail 同时指向它。
误区：链表拼接后不用更新 tail。 旧 tail 已经不是整条链的尾，必须更新成被拼接链表的尾。
追问：队列为什么常用头尾指针？ 出队从头删 O(1)，入队从尾加 O(1)，刚好符合先进先出。
追问：频繁删尾应该用什么？ 用双向链表，尾节点可以通过 prev 找到前驱，才能做到 O(1) 删除尾。

八、加强记忆

尾指针是一种小而实用的状态缓存：它把“找尾巴”这件重复劳动提前保存下来。面试时答清三句话就够稳：尾插 O(1)、拼接 O(1)、单链表删尾仍不是 O(1)。再补上空链表时头尾同改，就能体现你不只会背复杂度，还懂状态维护。

简化版

详细版