原题网址：https://www.lintcode.com/problem/nth-to-last-node-in-list/description
描述
找到单链表倒数第n个节点，保证链表中节点的最少数量为n。
您在真实的面试中是否遇到过这个题？ 是
样例
给出链表 3->2->1->5->null和n = 2，返回倒数第二个节点的值1.
标签
链表
Cracking The Coding Interview
思路：首先应该清楚，若链表一共有t个结点，则正数第n个结点即倒数第t+1-n个结点。反过来也一样，倒数第n个结点是正数第t+1-n个结点。
明白这点后可以使用两根指针cur 、pre来操作。其中一个指针cur走n步，指向第n个结点；
此时若cur的下一个结点为空，说明n为节点总数，直接返回头结点；
不为空，cur继续向前走一直走到尾节点，同时pre与cur同步向后，一共走了（t-n）步，此时pre指向第 1+t-n个结点（初始pre指向head），即倒数第n个结点。
AC代码：
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/ class Solution {
public:
/*
* @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) {
// write your code here
if (n==||head==NULL)
{
return head;
}
ListNode l();
l.next=head;
ListNode *cur=&l;
ListNode *pre=head;
for (int i=;i<n;i++)//循环n次，cur指向第n个结点;
{
cur=cur->next;
}
while(cur->next!=NULL)//n不为结点总数（cur不为尾节点）;
{
cur=cur->next;
pre=pre->next;
}//pre与cur走了（t-n）步，pre指向第t-n+1个结点，即倒数第n个结点;
return pre;
}
};
若初始pre指向l，pre指向第t-n个结点，即倒数第n+1个结点，最后返回pre->next。
或者初始cur与pre均指向head，则cur可循环n-1次，指向第n个结点。然后cur走到尾节点，循环t-n次，pre跟着走，指向第1+t-n个结点，即倒数第n个结点。