双指针法查找链表倒数第N个节点：先让快指针走N步，再同步移动，快指针到末尾时慢指针指向目标节点；需处理链表长度不足N或空链表等情况。
在C++中查找链表的倒数第N个节点，最常用的方法是双指针法（也叫快慢指针法）。这种方法时间复杂度为O(n)，空间复杂度为O(1)，效率高且实现简单。
基本思路：双指针法
定义两个指针，快指针和慢指针，初始都指向链表头节点。先让快指针向前移动N步，然后两个指针同时向后移动，直到快指针到达链表末尾。此时慢指针所指的节点就是倒数第N个节点。
注意事项：
- 如果链表长度小于N，说明倒数第N个节点不存在，应返回空指针或做相应处理。
- 需要判断空链表或N为0的情况。
代码实现
以下是完整的C++实现示例：
立即学习“C++免费学习笔记（深入）”；
struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };
ListNode findFromEnd(ListNode head, int n) {
if (!head || n }
ListNode* fast = head;
ListNode* slow = head;
// 快指针先走n步
for (int i = 0; i < n; i++) {
if (!fast) return nullptr; // 链表长度不足n
fast = fast->next;
}
// 快慢指针一起走，直到快指针到末尾
while (fast) {
fast = fast->next;
slow = slow->next;
}
return slow; // slow指向倒数第n个节点
使用示例
假设有一个链表：1 → 2 → 3 → 4 → 5，查找倒数第2个节点（即值为4的节点）：
int main() { ListNode* head = new ListNode(1); head->next = new ListNode(2); head->next->next = new ListNode(3); head->next->next->next = new ListNode(4); head->next->next->next->next = new ListNode(5);
ListNode* result = findFromEnd(head, 2);
if (result) {
std::cout << "倒数第2个节点的值是: " << result->val << std::endl;
} else {
std::cout << "节点不存在" << std::endl;
}
return 0;}
常见问题与优化
实际应用中需注意以下几点：
- 边界检查：确保n合法，链表非空。
- 内存安全：避免访问空指针，特别是在循环中判断fast是否为空。
- 若频繁查询，可考虑将链表转为数组，但会增加空间开销。
基本上就这些。双指针法简洁高效，是解决此类问题的标准做法。
