给定一个链表和一个数字n，返回该链表的倒数第n个节点的值。
比如，当输入如下且n=3，则输出为“B”
g
方法1
1）计算链表的长度len
2） 打印从链表开头起的第（len – n + 1）个节点
代码如下
class LinkedList {
Node head; // head of the list
/* Linked List node */
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* 打印链表的倒数第n个节点 */
void printNthFromLast(int n)
{
int len = 0;
Node temp = head;
// 1) 结算链表节点数
while (temp != null) {
temp = temp.next;
len++;
}
if (len < n)
return;
temp = head;
// 2) 获取从链表头开始的第 (len-n+1)个节点
for (int i = 1; i < len - n + 1; i++)
temp = temp.next;
System.out.println(temp.data);
}
/* 添加新节点到链表头 */
public void push(int new_data)
{
/* 1 & 2:生成新节点 */
Node new_node = new Node(new_data);
/* 3. 将新节点的next指向head */
new_node.next = head;
/* 4. 将head指向新节点 */
head = new_node;
}
/*驱动测试函数 */
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(35);
llist.printNthFromLast(4);
}
}
输出：
35
以下是相同方法的递归C代码。
void printNthFromLast(struct Node* head, int n)
{
static int i = 0;
if (head == NULL)
return;
printNthFromLast(head->next, n);
if (++i == n)
printf("%d", head->data);
}
时间复杂度： O（n），其中n是链表的长度。
方法2（使用两个指针）
维护两个指针–ref_Ptr和main_Ptr。初始化ref_Ptr和main_Ptr指向head节点。首先，将ref_Ptr从头移动n个节点。现在，将两个指针一一移动，直到ref_Ptr到达终点（为NULL）为止。现在，main_Ptr将从末尾算起指向第n个节点，返回main_Ptr即可。
class LinkedList {
Node head; // head of the list
/* Linked List node */
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Function to get the nth node from end of list */
void printNthFromLast(int n)
{
Node main_ptr = head;
Node ref_ptr = head;
int count = 0;
if (head != null) {
while (count < n) {
if (ref_ptr == null) {
System.out.println(n + " is greater than the no "
+ " of nodes in the list");
return;
}
ref_ptr = ref_ptr.next;
count++;
}
while (ref_ptr != null) {
main_ptr = main_ptr.next;
ref_ptr = ref_ptr.next;
}
System.out.println("Node no. " + n + " from last is " + main_ptr.data);
}
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*Drier program to test above methods */
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(20);
llist.push(4);
llist.push(15);
llist.push(35);
llist.printNthFromLast(4);
}
}
输出：
Node no. 4 from last is 35
