双指针法可高效查找链表倒数第N个节点：先让快指针走N步，再同步移动，当快指针到末尾时，慢指针指向目标节点；需处理N超长或小于1的边界情况。
在C++中查找链表的倒数第N个节点，常用的方法是双指针（快慢指针）技巧。这种方法时间复杂度为O(n)，空间复杂度为O(1)，效率高且实现简洁。
基本思路：双指针法
使用两个指针fast和slow，初始都指向链表头节点。先让fast指针向前移动N步，然后两个指针同时向后移动，直到fast到达链表末尾。此时slow所指节点即为倒数第N个节点。
关键点：
- 如果链表长度小于N，返回空或报错。
- 当fast移动了N步后，slow与fast之间正好相差N个节点。
- 当fast->next == nullptr时停止，确保slow停在目标节点上。
链表节点定义
struct ListNode {int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
查找倒数第N个节点的函数实现
ListNode* findNthFromEnd(ListNode* head, int n) {if (!head || n < 1) return nullptr;
ListNode *fast = head, *slow = head;
// 快指针先走n步
for (int i = 0; i < n; ++i) {
if (!fast) return nullptr; // n超过链表长度
fast = fast->next;
}
// 快慢指针一起走，直到快指针到末尾
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
return slow; // slow指向倒数第n个节点
}
使用示例
int main() {// 创建链表 1->2->3->4->5
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 = findNthFromEnd(head, 2);
if (result) {
std::cout << "倒数第2个节点值: " << result->val << std::endl; // 输出 4
} else {
std::cout << "未找到节点" << std::endl;
}
return 0;
}
基本上就这些。双指针法避免了遍历两次链表，是解决这类问题的标准做法。注意边界判断，比如n为0或大于链表长度的情况，防止访问空指针。
立即学习“C++免费学习笔记（深入）”；
