从零开始写算法——链表篇4:删除链表的倒数第 N 个结点 + 两两交换链表中的节点
链表（Linked List）一直是让人爱恨交加的数据结构。爱它是因为结构简单，恨它是因为指针操作稍有不慎就会导致断链或空指针异常。
今天通过两个经典场景——删除链表的倒数第 N 个结点和两两交换链表中的节点，来探讨链表操作中的两个通用范式：固定间距的双指针，以及基于多指针的局部拓扑重构。
场景一：删除链表的倒数第 N 个结点
这道题是“快慢指针”思想的经典应用。通常我们要删除倒数第 N 个节点，朴素的做法是先遍历一遍求长度 L，再遍历一遍找到第 L-N 个节点。但这需要两趟扫描。
如何通过一趟扫描完成任务？核心在于**“构建固定窗口”**。
核心思路
我们可以想象在链表上有一个长度为 n 的“尺子”或者“窗口”：
让 right 指针先走 n 步。
此时 right 和 left 之间隔了 n 个节点。
然后 left 和 right 同时向后移动，直到 right 抵达链表末尾。
此时，left 指针所在的位置，正好是倒数第 N 个节点的前驱节点。
C++ 代码实现
C++代码实现：
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { // 技巧：使用栈上分配的 Dummy Node，避免内存管理麻烦且处理了头删边缘情况 ListNode dummy(0, head); ListNode* right = &dummy; ListNode* left = &dummy; // 1. 构建间距：先让 right 走 n 步 for(int i = 0; i < n; ++i) { right = right->next; } // 2. 整体平移：直到 right 指向最后一个节点 // 注意：这里我们让 right 停在最后一个节点，而不是 null // 这样 left 正好停在待删除节点的前一个节点 while (right->next) { left = left->next; right = right->next; } // 3. 删除操作 ListNode* toDelete = left->next; left->next = left->next->next; // 在实际工程中建议 delete toDelete，刷题场景可忽略 return dummy.next; } };为什么一定要用 Dummy Node？
在链表操作中，哨兵节点（Dummy Node）非常实用。 如果不使用 dummy，当我们要删除的是**头节点（倒数第 L 个）**时，left 指针应该停在头节点的前面，但实际不存在这个节点，就需要写额外的 if 逻辑判断。 使用了 dummy 后，dummy->next 指向 head，即便是删除头节点，也变成了“删除 dummy 的下一个节点”，逻辑瞬间统一，无需处理边缘情况。
复杂度分析
时间复杂度：O(L)。其中 L 是链表长度。我们只对链表进行了一次遍历。
空间复杂度：O(1)。只使用了 dummy, left, right 等常数个额外空间。
场景二：两两交换链表中的节点
如果说上一题是对遍历技巧的运用，这道题考验的就是微观的**“指针手术”**。我们需要在不改变节点值（Val）的情况下，通过修改 next 指针来改变链表的拓扑结构。
核心思路：四指针定点操作
链表交换最怕的是断链。当我们交换两个节点 A 和 B 时，不仅要处理 A 和 B 之间的连接，还要处理 A 的前驱节点和 B 的后继节点。
我们可以定义四个指针，清晰地锁定了整个操作区域：
cur0: 前驱节点 (Prev)
cur1: 待交换节点 A (First)
cur2: 待交换节点 B (Second)
cur3: 后继节点 (Next)
C++ 代码实现
C++代码实现：
class Solution { public: ListNode* swapPairs(ListNode* head) { // 同样使用 Dummy Node 处理头节点交换的情况 ListNode dummy(0, head); ListNode* cur0 = &dummy; // 前驱 ListNode* cur1 = cur0->next; // 当前第一个 // 终止条件：必须要有两个节点才能交换 (cur1 && cur1->next) while (cur1 && cur1->next) { // 定位 cur2 和 cur3 ListNode* cur2 = cur1->next; ListNode* cur3 = cur2->next; // --- 核心交换逻辑 (三步走) --- cur0->next = cur2; // 1. 前驱指向第二个 cur2->next = cur1; // 2. 第二个指向第一个 cur1->next = cur3; // 3. 第一个指向后续 // --- 准备下一轮迭代 --- // 此时链表顺序已变为 0->2->1->3 // 下一轮的前驱 cur0 应该是当前的 cur1 (因为它被换到了后面) cur0 = cur1; // 下一轮的第一个节点应该是 cur3 cur1 = cur3; } return dummy.next; } };变量命名的逻辑
虽然在工程中我们习惯用 prev, curr, next 命名，但在涉及超过 3 个节点的复杂变换中，使用 cur0, cur1, cur2, cur3 这种序列化命名反而更清晰。它直观地展示了节点在原链表中的物理顺序，让**“谁指向谁”**的逻辑变得一目了然。
在循环迭代时，cur0 = cur1和cur1 = cur3这两行代码非常关键，它实现了“滑动窗口”向后平移两位的效果。
复杂度分析
时间复杂度：O(L)。我们需要遍历链表中的每一个节点一次。
空间复杂度：O(1)。虽然定义了4个指针变量，但这属于常数级别的额外空间，不随链表长度增加。
总结
这两个场景虽然解法不同，但背后的核心思想是一致的：
哨兵节点（Dummy Node）是处理链表边界的最佳实践。无论是删除倒数节点还是交换头节点，它都能让代码逻辑高度统一。
多指针辅助。不要吝啬定义指针变量。在复杂的链表操作中，明确定义出涉及到的所有节点（前驱、当前、目标、后继），比在代码里写一堆 head->next->next->next 要清晰得多，也更不容易出错。