在计算机科学中，链表是一种常见的数据结构，用于存储一系列有序的数据元素。这些元素在内存中不是连续存放的，而是通过指针互相连接。在处理链表时，有时我们需要找到链表中的特定位置的节点，比如倒数第n个节点。本文介绍了两种不同的方法来实现这个目标，这两种方法都是针对单向链表的。
方法一：利用两个指针
这种方法的核心思想是使用两个指针p和q，初始时都指向链表的头部。将指针q向后移动n个位置，然后同时移动p和q，直到q到达链表的末尾。此时，指针p会停在倒数第n个节点上。以下是对应的Java代码实现：
```java
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode findNthToLast(ListNode head, int n) {
if (head == null || n < 1) {
return null;
}
ListNode p = head, q = head;
while (q != null && n-- > 0) {
q = q.next;
}
if (n >= 0) {
return null;
}
while (p != null && q != null) {
p = p.next;
q = q.next;
}
return p;
}
```
在这个代码中，我们首先检查输入是否有效（链表不为空且n大于0）。然后，我们让q先走n步，如果n大于链表长度，就返回null，表示找不到倒数第n个节点。同步移动p和q，当q到达链表尾部时，p的位置就是倒数第n个节点。
方法二：计算链表的总长度
这种方法首先遍历整个链表一次，得到链表的总节点数m，然后找到倒数第n个节点实际上是找到第m - n + 1个节点。这个方法的思路与方法一类似，只是执行步骤稍有不同。下面是这种方法的Java代码实现：
```java
public ListNode nthToLast(ListNode head, int n) {
if (head == null || n < 1) {
return null;
}
ListNode p1 = head;
ListNode p2 = head;
int length = 0;
while (p2 != null) {
length++;
p2 = p2.next;
}
if (length < n) {
return null; // not found since list size < n
}
p1 = head;
for (int j = 0; j < length - n; ++j) {
p1 = p1.next;
}
return p1;
}
```
这个方法首先计算链表的长度，之后遍历链表找到倒数第n个节点。注意，如果链表长度小于n，也会返回null，表示无法找到倒数第n个节点。
这两种方法各有优缺点。方法一在空间复杂度上较低，只需要两个额外的指针，但可能需要遍历两次链表。而方法二虽然只需要遍历一次链表，但需要额外存储链表的长度，因此空间复杂度相对较高。在实际应用中，根据具体场景和性能要求，可以选择适合的方法。
