链表基础概念（哨兵节点 · 基本操作）

为什么要用链表

链表适合频繁插入删除但不需要随机访问的场景。

哨兵节点（Dummy Node）

哨兵节点是解决链表边界情况的万能技巧。

在链表头部前添加一个哑节点，避免对头节点的特殊处理：

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;

// 操作 cur.next，而非 cur
// 最终返回 dummy.next（新链表头）

适用场景：删除头节点、合并链表、需要操作链表头部时。

基本操作模板

在指定位置插入

// 在 prev 之后插入 newNode
void insertAfter(ListNode prev, ListNode newNode) {
    newNode.next = prev.next;
    prev.next = newNode;
}

删除某节点

// 删除 prev 之后的节点
void deleteAfter(ListNode prev) {
    if (prev.next != null) prev.next = prev.next.next;
}

// 直接删除当前节点（需要下一节点存在）
void deleteSelf(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

链表遍历技巧

找中间节点（快慢指针）

// 偶数长度时 slow 在前半段最后
ListNode findMid(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

获取链表长度

int getLength(ListNode head) {
    int len = 0;
    while (head != null) { len++; head = head.next; }
    return len;
}

常见错误

1. 空指针：操作前检查 node != null && node.next != null
2. 未保存 next：修改 curr.next 前先保存 next = curr.next
3. 忘记返回 dummy.next：使用哨兵节点后记得返回 dummy.next

调试技巧

打印链表方便调试：

static String listToString(ListNode head) {
    StringBuilder sb = new StringBuilder("[");
    while (head != null) {
        sb.append(head.val);
        if (head.next != null) sb.append(" -> ");
        head = head.next;
    }
    return sb.append("]").toString();
}