2.2 实现一个算法，找到单链表中倒数第k个节点。
这道题的考点在于我们怎么在一个单链表中找到倒数第n个元素？ 由于是单链表，所以我们没办法从最后一个元素数起，然后数n个得到答案。 但这种最直观的思路显然是没错的，那我们有没有办法通过别的方式，从最后的元素数起数 n个来得到我们想要的答案呢。
这个次序颠倒的思路可以让我们联想到一种数据结构：栈。
我们如果遍历一遍单链表，将其中的元素压栈，然后再将元素一一出栈。那么， 第n个出栈的元素就是我们想要的。
那我们是不是需要显式地用栈这么一个结构来做这个问题呢？答案是否。看到栈，我们应当 要想到递归，它是一种天然使用栈的方式。所以，第一种解决方案用递归，让栈自己帮我 们从链表的最后一个元素数起。
思路很简单，如果指向链表的指针还未空，就不断递归。当指针为空时开始退递归，这个过 程n不断减1，直接等于1，即可把栈中当前的元素取出。代码如下：
node *pp; int nn; void findNthToLast1(node *head){ if(head==NULL) return; findNthToLast1(head->next); if(nn==1) pp = head; --nn; }
虽然我们没办法从单链表的最后一个元素往前数，但如果我们维护两个指针， 它们之间的距离为k。然后，我将这两个指针同步地在这个单链表上移动，保持它们的距离 为k不变。那么，当第二个指针指到空时，第一个指针即为所求。很tricky的方法， 将这个问题很漂亮地解决了。
C++实现代码：
#include<iostream> #include<new> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x):val(x),next(NULL) {} }; void createList(ListNode *&L) { int arr[10]= {1,2,3,2,5,6,7,3,9,1}; int i; ListNode *p=NULL; for(i=0; i<10; i++) { ListNode *tmp=new ListNode(arr[i]); if(L==NULL) { L=tmp; p=tmp; } else { p->next=tmp; p=tmp; } } } ListNode *findKNode(ListNode *L,int k) { if(L==NULL) return NULL; ListNode *p=L; ListNode *q=L; int count=0; while(q) { if(count==k) { p=p->next; q=q->next; } else { count++; q=q->next; } } if(count==k) return p; else return NULL; } int main() { ListNode *head=NULL; createList(head); ListNode *p=head; while(p) { cout<<p->val<<" "; p=p->next; } cout<<endl; p=findKNode(head,11); if(p) cout<<p->val<<endl; }
