面试数据结构：链表

链表通过指针连接节点，不要求连续内存。

基本节点

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

常见题型

• 反转链表。
• 合并有序链表。
• 判断环。
• 找中点。
• 删除倒数第 N 个节点。

快慢指针

快慢指针常用于找中点和检测环。

如果快指针每次走两步，慢指针每次走一步，相遇说明存在环。

链表题的关键是画图

链表没有下标，所有操作都依赖指针关系。做题时不要急着写代码，先画出 prev、cur、next 三个指针的位置。

反转链表的核心就是不断改变 cur->next：

ListNode* prev = nullptr;
ListNode* cur = head;
while (cur) {
    ListNode* next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
}
return prev;

dummy 节点

涉及删除头节点、合并链表、插入节点时，dummy 节点能减少特殊判断。

ListNode dummy{0};
ListNode* tail = &dummy;

最后返回 dummy.next。这个技巧在面试里非常实用。