版权声明：本文为博主原创文章，未经博主允许不得转载。
难度：容易
要求：
找到单链表倒数第n个节点，保证链表中节点的最少数量为n
样例
给出链表** 3->2->1->5->null**和n = 2，返回倒数第二个节点的值1.
思路：
先翻转，再计算
/**
* @param head: The first node of linked list.
* @param n: An integer.
* @return: Nth to last node of a singly linked list.
*/
ListNode nthToLast(ListNode head, int n) {
if(head == null){
return null;
}
head = reverse(head);
int index = 1;
while(head.next != null){
if(index++ == n){
break;
}
head = head.next;
}
return head;
}
/**
* 原地翻转
*/
private ListNode reverse(ListNode head){
ListNode prev = null;
while(head != null){
ListNode tmp = head.next;
head.next = prev;
prev = head;
head = tmp;
}
return prev;
}
思路：
双指针，第一个指针先走n个，然后第一个指针和第二个指针同时往右遍历，当第一个指针为null时，第二个指针就为倒数第n个元素
/**
* @param head: The first node of linked list.
* @param n: An integer.
* @return: Nth to last node of a singly linked list.
*/
ListNode nthToLast(ListNode head, int n) {
if(head == null){
return null;
}
ListNode dummy = head;
for(int i = 0; i < n; i++){
if(head == null){
return null;
}
head = head.next;
}
ListNode pre = dummy;
while(head != null){
head = head.next;
pre = pre.next;
}
return pre;
}
