Java 中链表倒数第 N 个节点

这是一个非常有趣的问题，经常出现在顶级 IT 公司（如 Google、Amazon、TCS、Accenture 等）的面试中。通过解决这个问题，面试官希望考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将使用不同的方法和逻辑来获取 Java 中链表的倒数第 n 个节点。此外，我们还将创建相应的 Java 程序。

问题陈述

给定一个单向链表和一个值 N。我们的任务是计算倒数第 N 个节点的值。倒数意味着参考点是从最右边的节点开始，这使得问题变得棘手。这是因为在单向链表中，只能单向遍历。请注意，N 的值总是小于或等于链表的长度。请观察以下示例。

示例 1

输入： 19 -> 56 -> 45 -> 32 -> 10 -> 70 -> NULL, N = 2

输出 10

解释： 给定链表倒数第二个节点是节点 10。

示例 2

输入： 119 -> 156 -> 15 -> 312 -> 101 -> 710 -> NULL, N = 5

输出 156

解释： 给定链表倒数第五个节点是节点 156。

问题解决方案

方法：使用栈

我们知道堆栈以 Last In First Out (LIFO) 方式工作。因此，当需要计算链表的倒数第 n 个节点时，堆栈工作得很好。我们所要做的就是将所有节点存储在堆栈中，然后从堆栈中移除 n 个节点。移除的第 n 个节点的值就是我们的答案。

文件名： NthNodeEnd.java

输出

For the following linked list
19 56 45 32 10 70 
The 2nd node from the end is: 10

For the following linked list
19 119 156 15 312 101 710 
The 5th node from the end is: 156

复杂性分析： 上述程序的时间复杂度为 O(s)。由于程序使用堆栈存储节点，因此程序的空间复杂度也为 O(s)，其中 s 是给定链表中存在的节点总数。

我们仍然可以在空间复杂度方面进行一些优化。请观察以下方法。

方法：使用链表的长度

我们知道，从左到右遍历单向链表很容易。为了反向遍历链表，我们在上述方法中使用了堆栈。如果我们仔细观察链表，我们会发现倒数第二个节点是正数第五个节点（参见示例 1），而倒数第五个节点是正数第二个节点（参见示例 2）。通过查看这两个示例，我们可以推导出计算倒数第 n 个节点的公式。该公式是

倒数第 N 个节点是正数 (s - n + 1) 个节点，其中 s 是链表中存在的节点总数。因此，倒数第二个节点是正数 (6 - 2 + 1) = 5 个节点（6 是示例 1 中提到的链表大小）。因此，该方法很简单。我们所要做的就是计算链表的总长度。请观察以下程序。

文件名： NthNodeEnd.java

输出

For the following linked list
19 56 45 32 10 70 
The 2nd node from the end is: 10

For the following linked list
19 119 156 15 312 101 710 
The 5th node from the end is: 156

复杂性分析： 上述程序的时间复杂度与上一个程序相同。由于程序不使用任何数据结构，因此程序的空间复杂度为 O(1)。