Python中链表中倒数第N个节点

链表是计算机科学和编程中的基本数据结构。与在内存中连续存储数据的数组不同，链表由通过指针链接在一起的节点组成。这使得节点能够高效地插入和删除，从而使链表可用于实现堆栈、队列和其他抽象数据类型。

链表上一个常见的操作是查找倒数第 n 个节点。这允许您访问相对于尾部的节点，而无需遍历整个列表。在 Python 中，链表通常使用类来实现节点对象。我们可以编写函数来遍历节点并计算列表的长度。通过从头节点重复必要的步数，我们可以确定倒数第 n 个目标节点。

本文将演示如何使用 Python 实现来获取链表中倒数第 n 个节点。我们将介绍构建一个函数来遍历到目标节点、确定列表长度以及表示节点的基础知识。掌握这些基础知识将为您打下坚实的基础，以使用链表解决更高级的算法和数据结构。

链表

链表是一种线性数据结构，由通过指针链接在一起的节点组成。每个节点包含两部分：

1. 数据 - 节点中存储的实际数据。这可以是整数、字符串、对象或数据类型。
2. 指针 - 指向列表中下一个节点的引用或指针。最后一个节点的指针指向 null，表示列表的结尾。

链表与数组不同，数组中的所有元素都按顺序存储在内存中。链表最显著的优点是节点插入和删除的效率，因为您只需要更新相邻节点的指针，而无需在内存中移动元素。

节点通过每个节点存储指向下一个节点的指针或引用来链接在一起。这个节点链构成了链表。链表的入口点称为头。您从头开始遍历列表，然后沿着指针直到到达列表末尾（null）。

链表的一些关键特征：

• 节点存储数据和指向下一个节点的指针
• 节点插入/删除效率高
• 访问时间是线性的 - O(n) - 必须遍历列表
• 动态大小
• 非连续内存分配

示例链表结构

方法 1：朴素方法

查找链表中倒数第 n 个节点是一个常见的面试问题和编程练习。它考验了开发人员对链表遍历和操作的理解。

解决此问题的一种朴素方法是遍历整个链表以确定其长度。然后，从头开始再次遍历 (length - n) 步，即可到达倒数第 n 个所需节点。

例如，给定以下简单链表：

要查找倒数第 3 个节点，我们首先遍历并确定长度为 5。然后，从头开始，遍历 (5 - 3 = 2) 步，即可到达节点 [3]。

这涉及遍历列表两次以计算长度，然后再遍历一次以找到第 n 个节点。关键步骤是：

1. 遍历一次并计数节点以确定长度
2. 验证 n 是否在边界内
3. 再次从头开始遍历 (length - n) 步

虽然简单，但这需要 O(N) 时间，因为在最坏情况下我们必须遍历所有 N 个节点两次。我们稍后将探讨一种更优化的单次遍历解决方案。首先，让我们根据提供的代码片段回顾一下 Python 中这种朴素方法的实现。

输出

The 3th node from the end is: 3

说明

1. 定义了一个 ListNode 类来表示链表中的每个节点。它包含一个 value 字段来存储数据，以及一个 next 字段来指向下一个节点。
2. find_nth_from_end 函数以头节点和 n 作为参数来查找链表中倒数第 n 个节点。
3. 它首先通过从头遍历并计数节点来计算链表的长度。
4. 然后，它检查 n 是否超出长度，因为这会越界。
5. 接下来，它从头开始遍历列表，正好遍历 length - n 步，以到达倒数第 n 个节点。
6. 如果找到，则返回此节点。否则，返回 None。
7. 定义了一个辅助函数 print_linked_list，用于整洁地打印给定头节点的列表。
8. 在主部分：
   1. 通过链接 ListNode 对象创建了一个示例链表。
   2. 调用 find_nth_from_end 来查找倒数第 3 个节点。
   3. 如果找到结果，则打印结果，否则打印一条消息，说明 n 超出范围。

方法 2：递归

链表通常使用迭代、基于循环的算法进行遍历和操作。然而，递归也可以有效地用于链表问题。

其中一个问题是查找单向链表中倒数第 n 个节点。我们可以实现一个递归解决方案，用代码的简洁性来换取空间复杂度。

关键步骤是：

• 递归遍历列表，同时增加计数器
• 当达到列表末尾的基本情况时，返回
• 随着堆栈展开，检查 counter == n 以查找第 n 个节点

例如，给定链表：

Head -> [1] -> [2] -> [3] -> [4] -> [5] -> null

要查找倒数第 3 个节点，我们递归地遍历，增加计数，并返回计数达到 3 的节点。

直观地说，递归会将控制流转移到基本情况，然后在调用堆栈向上回溯时反向重建问题。

与使用循环进行迭代相比，递归提供了一种封装控制流和调用堆栈中的临时变量的优雅方法。但是，它以更高的内存使用为代价，这可能导致堆栈溢出错误。

输出

The 3th node from the end is: 3

说明

1. ListNode 类代表链表中的每个节点。
2. find_nth_from_end_recursive 函数以头节点和 n 作为参数。
3. 它每次都通过传递下一个节点来递归调用自身。
4. 在每次调用中，它都会增加一个计数变量。
5. 当到达列表末尾（head 为 None）时，基本情况命中。
6. 当调用返回时，计数代表从末尾开始的当前位置。
7. 如果 count 等于 n，则该节点是倒数第 n 个节点。
8. 返回此节点和更新的计数。
9. 最后，如果找到，初始调用将返回第 n 个节点，否则返回 None。
10. 一个辅助打印函数可以整洁地显示链表。
11. 在 main() 中：
    1. 创建了一个示例链表。
    2. 调用 find_nth_from_end_recursive。
    3. 如果找到，则打印结果，否则打印一条消息。