版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載菇晃。
難度：容易
要求：
找到單鏈表倒數(shù)第n個(gè)節(jié)點(diǎn)蹦疑，保證鏈表中節(jié)點(diǎn)的最少數(shù)量為n
樣例
給出鏈表** 3->2->1->5->null**和n = 2乓搬，返回倒數(shù)第二個(gè)節(jié)點(diǎn)的值1.
思路：
先翻轉(zhuǎn)，再計(jì)算
/**
* @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;
}
/**
* 原地翻轉(zhuǎn)
*/
private ListNode reverse(ListNode head){
ListNode prev = null;
while(head != null){
ListNode tmp = head.next;
head.next = prev;
prev = head;
head = tmp;
}
return prev;
}
思路：
雙指針代虾，第一個(gè)指針先走n個(gè)进肯，然后第一個(gè)指針和第二個(gè)指針同時(shí)往右遍歷，當(dāng)?shù)谝粋€(gè)指針為null時(shí)棉磨，第二個(gè)指針就為倒數(shù)第n個(gè)元素
/**
* @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;
}
