C++中链表倒数第N个节点的查找方法

双指针法查找链表倒数第N个节点：先让快指针走N步，再同步移动，快指针到末尾时慢指针指向目标节点；需处理链表长度不足N或空链表等情况。

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

基本思路：双指针法

定义两个指针，快指针和慢指针，初始都指向链表头节点。先让快指针向前移动N步，然后两个指针同时向后移动，直到快指针到达链表末尾。此时慢指针所指的节点就是倒数第N个节点。

注意事项：

• 如果链表长度小于N，说明倒数第N个节点不存在，应返回空指针或做相应处理。
• 需要判断空链表或N为0的情况。

代码实现

以下是完整的C++实现示例：

struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };

ListNode findFromEnd(ListNode head, int n) { if (!head || n <= 0) return nullptr;

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是否为空。
• 若频繁查询，可考虑将链表转为数组，但会增加空间开销。

基本上就这些。双指针法简洁高效，是解决此类问题的标准做法。

本文转载于：互联网 如有侵犯，请联系zhengruancom@outlook.com删除。
免责声明：正软商城发布此文仅为传递信息，不代表正软商城认同其观点或证实其描述。