答案，注意，一种是递归，另一种是迭代，那么巧妙利用双指针：
迭代：
public static LinkedListNode nthToLast(LinkedListNode head, int n) {
LinkedListNode p1 = head;
LinkedListNode p2 = head;
if (n <= 0) return null;
// Move p2 n nodes into the list. Keep n1 in the same position.
for (int i = 0; i < n - 1; i++) {
if (p2 == null) {
return null; // Error: list is too small.
}
p2 = p2.next;
}
if (p2 == null) { // Another error check.
return null;
}
// Move them at the same pace. When p2 hits the end,
// p1 will be at the right element.
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
递归：
public static int nthToLastR1(LinkedListNode head, int n) {
if (n == 0 || head == null) {
return 0;
}
int k = nthToLastR1(head.next, n) + 1;
if (k == n) {
System.out.println(n + "th to last node is " + head.data);
}
return k;
}