虚拟头尾节点（Dummy Head/Tail）
虚拟头尾节点是链表实现中的一种重要技巧，通过在链表中添加不存储真实数据的虚拟节点，简化边界条件处理。
核心思想
在创建链表时就创建虚拟头节点（dummyHead）和虚拟尾节点（dummyTail），无论链表是否为空，这两个节点都存在。
虚拟头尾节点的效果
空链表
dummyHead <-> dummyTail
添加元素 1, 2, 3 后
dummyHead <-> 1 <-> 2 <-> 3 <-> dummyTail
优势
| 优势 | 说明 |
|---|---|
| 统一操作逻辑 | 无需区分头部、尾部、中间插入/删除，都按中间节点处理 |
| 避免空指针 | 虚拟节点始终存在，不会出现 null 指针问题 |
| 简化代码 | 减少边界条件判断，代码更简洁 |
| 提高可维护性 | 逻辑统一，不易出错 |
适用场景
双链表（强烈推荐）
虚拟头尾节点对双链表非常有效：
- 虚拟头节点（dummyHead）：简化头部操作
- 虚拟尾节点（dummyTail）：简化尾部操作
- 两者配合，所有操作都统一为"在中间插入/删除"
单链表（部分有效）
- 虚拟头节点：有一定简化作用
- 虚拟尾节点：没有太大作用（单链表删除尾节点仍需遍历找前驱）
算法题中的虚拟头节点（单链表）
在算法题中，虚拟头节点广泛用于简化边界处理：
| 应用场景 | 说明 | 对应题目 |
|---|---|---|
| 合并两个有序链表 | 用dummy统一新链表的构建，避免处理空指针 | LeetCode 21 |
| 链表分解 | 用两个dummy分别管理两个子链表 | LeetCode 86 |
| 合并k个有序链表 | 用dummy构建结果链表 | LeetCode 23 |
| 删除倒数第N个节点 | 用dummy处理删除头节点的情况 | LeetCode 19 |
何时使用虚拟头结点（经验法则）：
当你需要创造一条新链表的时候（合并、分解等），使用虚拟头结点可以简化边界情况的处理。
参见：链表技巧总结
实现示例（双链表）
public class MyLinkedList<E> {
// 虚拟头尾节点（通常用 final 修饰）
final private Node<E> head, tail;
public MyLinkedList() {
this.head = new Node<>(null); // 虚拟头节点
this.tail = new Node<>(null); // 虚拟尾节点
head.next = tail;
tail.prev = head;
this.size = 0;
}
// 所有操作都基于这两个虚拟节点
// 头部插入：在 head 和 head.next 之间插入
// 尾部插入：在 tail.prev 和 tail 之间插入
// 中间插入：找到位置后，在前驱和后继之间插入
}
注意事项
1. 虚拟节点对外不可见
虚拟节点是内部实现细节，对外提供的 API（如 get(index)）应该从真实节点开始计算：
public E get(int index) {
checkElementIndex(index);
Node<E> p = head.next; // 从真实节点开始，跳过虚拟头节点
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.val;
}
2. 内存开销极小
虚拟节点只多占用一点内存（通常2个节点），比起给代码带来的简化，这点开销完全值得。
3. 不替代边界检查
虽然虚拟节点避免了空指针，但仍需检查索引合法性：
private void checkElementIndex(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException(...);
}