c++中如何查找链表倒数第N个节点_c++链表倒数第N节点查找方法-C++-PHP中文网

c++中如何查找链表倒数第N个节点_c++链表倒数第N节点查找方法

裘德小鎮的故事

发布： 2025-09-29 09:47:02

原创

367人浏览过

双指针法可高效查找链表倒数第N个节点：先让快指针走N步，再同步移动，当快指针到末尾时，慢指针指向目标节点；需处理N超长或小于1的边界情况。

c++中如何查找链表倒数第n个节点_c++链表倒数第n节点查找方法

在C++中查找链表的倒数第N个节点，常用的方法是双指针（快慢指针）技巧。这种方法时间复杂度为O(n)，空间复杂度为O(1)，效率高且实现简洁。

基本思路：双指针法

使用两个指针fast和slow，初始都指向链表头节点。先让fast指针向前移动N步，然后两个指针同时向后移动，直到fast到达链表末尾。此时slow所指节点即为倒数第N个节点。

关键点：

Cowriter

AI 作家，帮助加速和激发你的创意写作

107

查看详情

如果链表长度小于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++免费学习笔记（深入）”；

以上就是c++++中如何查找链表倒数第N个节点_c++链表倒数第N节点查找方法的详细内容，更多请关注php中文网其它相关文章！