【LeetCode刷题日志】链表删除与交换双经典：19.删除链表的倒数第N个结点 & 24.两两交换链表中的节点（C++详解）

【LeetCode刷题日志】链表删除与交换双经典：19.删除链表的倒数第N个结点 & 24.两两交换链表中的节点（C++详解）

文章包含完整的题目描述、前置知识、解题思路、C++ 代码逐行解释、复杂度分析、核心技巧、踩坑记录、可复用模板和学习感悟。

📑 目录

• 📋 本篇日志包含的题目
• 📖 开始前必须搞懂的 5 个概念
  • 概念1：什么是"倒数第N个结点"？
  • 概念2：为什么fast要先走n步？（快慢指针找倒数第N个）
  • 概念3：什么是递归回溯计数？
  • 概念4：两两交换的三步指针操作
  • 概念5：虚拟头节点（dummy）的作用
• 一、力扣 19. 删除链表的倒数第N个结点
  • 1.1 题目描述
  • 1.2 解题思路
  • 1.3 C++ 代码实现（逐行解释）
  • 1.4 复杂度分析
  • 1.5 核心技巧与踩坑记录
• 二、力扣 24. 两两交换链表中的节点
  • 2.1 题目描述
  • 2.2 解题思路
  • 2.3 C++ 代码实现（逐行解释）
  • 2.4 复杂度分析
  • 2.5 核心技巧与踩坑记录
• 三、两题关联与进阶思考
  • 3.1 从 19 到 24 的链表指针操作思维跃迁
  • 3.2 可复用模板汇总（其他题目直接套用）
• 四、刷题心得与学习感悟
  • 4.1 这两题能学到什么？
  • 4.2 高频算法总结
  • 4.3 新手常见误区
  • 4.4 我的刷题方法分享
• 五、总结

📋 本篇日志包含的题目

💡 为什么把这两题放在一起？ 第19题教你"如何找到并删除倒数第N个节点"，核心是快慢指针的"速度差"思想；第24题教你"如何两两交换相邻节点"，核心是虚拟头节点+三步指针操作。两题都涉及链表的指针修改，而且都能用迭代和递归两种方法解决，对比学习效果更好。

📖 开始前必须搞懂的 5 个概念

这部分是给零基础同学准备的，如果你已经熟悉这些概念，可以直接跳到正文。

概念1：什么是"倒数第N个结点"？

链表是单向的，只能从头往后走，不能从尾往前走。那"倒数第N个"怎么找？

链表：1 → 2 → 3 → 4 → 5
倒数第1个 = 5（最后一个）
倒数第2个 = 4
倒数第3个 = 3

• 倒数第N个，就是从尾巴往回数第N个节点
• 因为链表不能往回走，所以需要用技巧来找

概念2：为什么fast要先走n步？（快慢指针找倒数第N个）

这是19题快慢指针法的核心思想：

设链表长度为 L，要找倒数第 n 个
那么倒数第 n 个的位置是第 L-n+1 个（从1开始数）

做法：

💡 关键：slow和fast都从dummy（虚拟头节点）开始，这样slow最终停在待删节点的前驱，方便删除。

概念3：什么是递归回溯计数？

19题的递归法用了一个很巧妙的思路：

• 先一路递归到链表末尾（head == nullptr时返回）
• 然后在回溯（从末尾往回走）的时候，用count计数
• count从0开始，每回溯一层count++
• 当count == n时，说明当前节点就是倒数第n个，返回head->next跳过它

递归深入：1 → 2 → 3 → 4 → 5 → nullptr
回溯计数：← count=1 ← count=2 ← count=3 ← count=4 ← count=5
(5) (4) (3) (2) (1)

回溯时count=1对应节点5（倒数第1个），count=2对应节点4（倒数第2个），以此类推。

概念4：两两交换的三步指针操作

24题迭代法中，交换node1和node2需要三步：

交换前：cur → node1 → node2 → node3

第一步：cur->next = node2（cur连到node2）

cur → node2 → node3
node1 ↗

第二步：node1->next = node2->next（node1连到node3）

cur → node2 → node3
node1 ↗ ↑
node1->next

第三步：node2->next = node1（node2连到node1）

cur → node2 → node1 → node3

交换完成！然后cur = node1，继续处理下一对。

概念5：虚拟头节点（dummy）的作用

19题和24题的迭代法都用了虚拟头节点：

ListNode* dummy = new ListNode(0, head);

为什么需要虚拟头节点？

• 19题：如果要删除的是头节点（倒数第n个正好是head），没有dummy的话删除头节点需要特殊处理。有了dummy，头节点和其他节点一样处理，统一返回dummy->next。
• 24题：交换第一对节点时，头节点会变（原来的第二个节点变成新的头节点）。有了dummy，cur从dummy开始，第一对和后面的对一样处理，统一返回dummy->next。

💡 一句话总结：虚拟头节点让"头节点的操作"和"其他节点的操作"统一起来，不需要写特殊的边界处理代码。

一、力扣 19. 删除链表的倒数第N个结点

1.1 题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
解释：删除倒数第2个节点（值为4的节点）

示例 2：

输入：head = [1], n = 1
输出：[]
解释：删除唯一的节点

示例 3：

输入：head = [1,2], n = 1
输出：[1]
解释：删除最后一个节点（值为2的节点）

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

进阶： 你能尝试使用一趟扫描实现吗？

1.2 解题思路

思路一：快慢指针法（fast先走n步）—— 推荐

核心思想： 用两个指针slow和fast，都从虚拟头节点dummy出发。先让fast先走n步，然后slow和fast同时走（每次都走一步），直到fast走到最后一个节点（fast->next == nullptr）。此时slow正好停在倒数第n个节点的前驱，删除slow->next即可。

为什么fast先走n步就能找到倒数第n个？

• 设链表长度为 L，fast先走n步后，fast在第n+1个位置（从dummy开始算）
• 然后slow和fast同时走，当fast->next == nullptr时，fast在最后一个节点
• fast从第n+1个位置走到最后一个节点，走了 L-n 步
• slow也走了 L-n 步，从dummy出发走 L-n 步，正好停在第 L-n 个位置
• 倒数第n个节点在第 L-n+1 个位置，所以slow是它的前驱！

手动模拟：以 [1→2→3→4→5], n=2 为例

链表：dummy → 1 → 2 → 3 → 4 → 5
要删除倒数第2个（节点4）

第一步：fast先走n=2步

fast现在在节点2。

第二步：slow和fast同时走，直到fast->next == nullptr

slow现在在节点3，正好是待删节点4的前驱！

第三步：删除slow->next（节点4）

slow->next = slow->next->next // 3 → 5，跳过4
delete delNode // 释放节点4

结果：dummy → 1 → 2 → 3 → 5 ✅

思路二：递归法（回溯计数）

核心思想： 先递归深入到链表末尾，然后在回溯的时候用count计数。count从0开始，每回溯一层count++。当count == n时，说明当前节点就是倒数第n个，返回head->next跳过它（相当于删除）；否则返回head。

为什么回溯时count==n就是倒数第n个？

• 递归深入到nullptr时开始回溯
• 回溯第一层（最后一个节点）count=1，对应倒数第1个
• 回溯第二层count=2，对应倒数第2个
• …
• 回溯第n层count=n，对应倒数第n个

手动模拟：以 [1→2→3→4→5], n=2 为例

递归深入阶段：

removeNthFromEnd(1,2)
→ removeNthFromEnd(2,2)
→ removeNthFromEnd(3,2)
→ removeNthFromEnd(4,2)
→ removeNthFromEnd(5,2)
→ removeNthFromEnd(nullptr,2) → 返回nullptr

回溯阶段（从下往上）：

最终返回节点1，链表变为 1→2→3→5 ✅

⚠️ 注意：count是类的成员变量，在递归过程中共享。每次调用函数count都会累加。

1.3 C++ 代码实现（逐行解释）

方法一：快慢指针法（fast先走n步）

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 创建虚拟头节点，next指向head
ListNode* dummy = new ListNode(0, head);
// slow和fast都从dummy开始
ListNode* slow = dummy;
ListNode* fast = dummy;

// fast先走n步
for (int i = 0; i < n; i++) {
fast = fast->next;
}

// slow和fast同时走，直到fast走到最后一个节点
while (fast->next != nullptr) {
slow = slow->next;
fast = fast->next;
}

// 此时slow是待删节点的前驱，删除slow->next
ListNode* delNode = slow->next; // 保存待删节点
slow->next = slow->next->next; // 跳过待删节点
delete delNode; // 释放内存

// 返回新的头节点
return dummy->next;
}
};

关键代码逐行解释：

方法二：递归法（回溯计数）

class Solution {
public:
// count是成员变量，在递归过程中共享
int count = 0;

ListNode* removeNthFromEnd(ListNode* head, int n) {
// 递归终止条件：走到末尾了
if (head == nullptr) {
return nullptr;
}

// 递归深入：先处理后面的节点
head->next = removeNthFromEnd(head->next, n);

// 回溯阶段：count++，从末尾往回数
count++;

// 如果count==n，说明当前节点是倒数第n个，返回head->next跳过它
if (count == n) {
return head->next;
}

// 否则正常返回当前节点
return head;
}
};

关键代码逐行解释：

1.4 复杂度分析

说明：

• L 是链表的长度
• 快慢指针法只遍历链表一次（fast先走n步，再和slow一起走L-n步，总共L步），满足题目"进阶：一趟扫描"的要求
• 递归法需要递归栈空间，空间O(L)

1.5 核心技巧与踩坑记录

核心技巧：

踩坑记录：

二、力扣 24. 两两交换链表中的节点

2.1 题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]
解释：第1对(1,2)交换→(2,1)，第2对(3,4)交换→(4,3)

示例 2：

输入：head = []
输出：[]
解释：空链表

示例 3：

输入：head = [1]
输出：[1]
解释：只有一个节点，无法交换

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

2.2 解题思路

思路一：迭代法（虚拟头节点+三步交换）—— 推荐

核心思想： 用虚拟头节点dummy，cur从dummy开始。每次处理cur后面的两个节点node1和node2，通过三步指针操作交换它们，然后cur移动到node1（交换后的第二个节点），继续处理下一对。

三步交换指针操作：

交换前：cur → node1 → node2 → node3

交换后：cur → node2 → node1 → node3

然后 cur = node1，继续处理下一对。

手动模拟：以 [1→2→3→4] 为例

初始：dummy → 1 → 2 → 3 → 4
cur = dummy

第一轮：交换node1=1和node2=2

第二轮：交换node1=3和node2=4

最终：dummy→2→1→4→3，返回dummy->next即节点2 ✅

思路二：递归法

核心思想： 递归处理每一对节点。对于当前的head和head->next（即node1和node2）：

递归终止条件： head为空或head->next为空（没有两个节点可以交换），直接返回head。

手动模拟：以 [1→2→3→4] 为例

递归深入阶段：

swapPairs(1)
→ newHead=2, head->next=swapPairs(3)
→ newHead=4, head->next=swapPairs(nullptr)
→ 返回nullptr

回溯阶段（从下往上）：

最终返回节点2，链表变为 2→1→4→3 ✅

2.3 C++ 代码实现（逐行解释）

方法一：迭代法（虚拟头节点+三步交换）

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// 创建虚拟头节点，next指向head
ListNode* dummy = new ListNode(0, head);
// cur从dummy开始，每次处理cur后面的两个节点
ListNode* cur = dummy;

// 只要cur后面还有两个节点，就继续交换
while (cur->next != nullptr && cur->next->next != nullptr) {
// 保存要交换的两个节点
ListNode* node1 = cur->next;
ListNode* node2 = cur->next->next;

// 三步交换指针
cur->next = node2; // 第一步：cur连到node2
node1->next = node2->next; // 第二步：node1连到node2后面的节点
node2->next = node1; // 第三步：node2连到node1

// cur移动到node1（交换后的第二个节点），准备处理下一对
cur = node1;
}

// 返回新的头节点
return dummy->next;
}
};

关键代码逐行解释：

方法二：递归法

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// 递归终止条件：没有节点或只有一个节点，无法交换
if (head == nullptr || head->next == nullptr) {
return head;
}

// 保存交换后的第一个节点（原来的第二个节点）
ListNode* newHead = head->next;

// 递归交换newHead后面的节点，把结果连到head后面
head->next = swapPairs(newHead->next);

// newHead连到head，完成当前这一对的交换
newHead->next = head;

// 返回交换后的新头
return newHead;
}
};

关键代码逐行解释：

2.4 复杂度分析

说明：

• n 是链表的长度
• 两种方法都只遍历链表一次，时间O(n)
• 迭代法只用了几个指针，空间O(1)
• 递归法需要递归栈空间，空间O(n)

2.5 核心技巧与踩坑记录

核心技巧：

踩坑记录：

三、两题关联与进阶思考

3.1 从 19 到 24 的链表指针操作思维跃迁

思维提炼： 这两题都是链表指针操作的经典题，而且都能用迭代和递归两种方法解决：

• 迭代法：19题用快慢指针的"距离差"找位置，24题用虚拟头节点+三步交换改指针。两题都必须用虚拟头节点来统一处理头节点的边界情况。
• 递归法：19题用"回溯计数"（深入时不做事，回溯时计数），24题用"newHead技巧"（先保存新头，递归处理后面，再连当前这一对）。两题的递归都利用了"回溯时从后往前处理"的特点。

对比学习这两题，能深刻理解"快慢指针距离差"和"三步交换指针"这两个链表操作的核心思想，以及迭代和递归两种思维方式的转换。

3.2 可复用模板汇总（其他题目直接套用）

从这两道题中，可以提炼出链表操作的 2 个固定模板。

模板一：快慢指针找倒数第N个（源自 19 题）

核心思想： fast先走n步制造距离差，然后slow和fast同速走，fast到末尾时slow就在倒数第n个的前驱。

// 模板：快慢指针找倒数第N个节点的前驱
// 适用：删除倒数第N个节点、找倒数第K个节点等
ListNode* findNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
ListNode* slow = dummy;
ListNode* fast = dummy;
// fast先走n步
for (int i = 0; i < n; i++) {
fast = fast->next;
}
// 同速走，fast到末尾时slow在目标前驱
while (fast->next != nullptr) {
slow = slow->next;
fast = fast->next;
}
return slow; // slow是倒数第n个节点的前驱
}

可直接套用的题目：

模板二：虚拟头节点+三步交换（源自 24 题）

核心思想： cur从dummy开始，每次处理cur后面的两个节点node1和node2，三步交换指针，cur=node1前进。

// 模板：虚拟头节点+三步交换相邻节点
// 适用：两两交换链表节点、K个一组反转链表等
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0, head);
ListNode* cur = dummy;
while (cur->next != nullptr && cur->next->next != nullptr) {
ListNode* node1 = cur->next;
ListNode* node2 = cur->next->next;
// 三步交换
cur->next = node2;
node1->next = node2->next;
node2->next = node1;
// 前进
cur = node1;
}
return dummy->next;
}

可直接套用的题目：

链表操作模板选择速查表

💡 小白建议：链表操作题，先想"要不要用虚拟头节点"（头节点会变或可能删头节点就一定要用），再想"用迭代还是递归"（迭代空间O(1)，递归代码简洁但空间O(n)）。虚拟头节点是链表题的万能神器，记住它！

四、刷题心得与学习感悟

4.1 这两题能学到什么？

4.2 高频算法总结

本篇的删除倒数第N个和两两交换，分别是"链表删除"和"链表交换/反转"两大基础题型。

4.3 新手常见误区

4.4 我的刷题方法分享

五、总结

本文详细讲解了 LeetCode 19（删除链表的倒数第N个结点）和 24（两两交换链表中的节点）两道经典链表操作题目：

• 19题：提供了两种解法——①快慢指针法：dummy虚拟头节点，slow和fast都从dummy出发，fast先走n步，然后同速走直到fast->next= =nullptr，此时slow是待删节点前驱，删除slow->next并delete释放内存；②递归法：成员变量count计数，递归深入到末尾后回溯，count++，count==n时返回head->next跳过该节点，否则返回head。快慢指针法 O(L) 时间 O(1) 空间（一趟扫描），递归法 O(L) 时间 O(L) 空间。
• 24题：提供了两种解法——①迭代法：dummy虚拟头节点，cur从dummy开始，while(cur后面有两个节点)时保存node1和node2，三步交换（cur->next=node2、node1->next=node2->next、node2->next=node1），cur=node1前进；②递归法：终止条件head或head->next为空，保存newHead=head->next，head->next=递归(newHead->next)，newHead->next=head，返回newHead。迭代法 O(n) 时间 O(1) 空间，递归法 O(n) 时间 O(n) 空间。
• 两题关系：两题都是链表指针操作的经典题，都必须用虚拟头节点统一处理头节点变化，都能用迭代和递归两种方法解决。19题的核心是快慢指针的"距离差"思想，24题的核心是"三步交换指针"。
• 可复用模板：从两题提炼出2个核心模板——“快慢指针找倒数第N个”（可套用到面试题02.02、1721、剑指Offer22等题）和"虚拟头节点+三步交换"（可套用到25、206、92等题）。

这两道题是链表操作的进阶必刷题，19题中等难度但快慢指针的距离差思想是链表题的核心，24题中等难度但三步交换指针是链表操作的基本功。希望这篇详解能帮助你理解快慢指针和三步交换的核心思想，也欢迎在评论区交流你的解法和心得！

下一篇预告： 继续链表专题，将讲解【83.删除排序链表中的重复元素】和【234.回文链表】（链表去重与判回文双经典），敬请期待！ 如果本文对你有帮助，欢迎点赞 👍、收藏 ⭐、关注我，一起在算法之路上进步！