题目：

输入一个链表，输出该链表中倒数第k个结点。

例如：链表中有6个结点，从头到尾依次为1,2,3,4,5,6，则该链表的倒数第3个结点为4.

链表结点定义：

struct ListNode{    int val;    ListNode* next;};

思路：

1、遍历整个链表，计算结点的个数，再遍历链表，找到第n-k+1个结点；

2、通过两个指针，第一个指针先走k-1步，到达第k个结点，第二个指针指向头结点，然后两个指针同时走，每次走一步，当第一个指针走到链尾时，第二个指针恰好走到倒数第k个结点。

注意细节：链表为空，k大于链表长度或者小于1等情况。

类似问题：

a. 求链表的中间结点，如果链表中结点数为奇数，则返回中间结点；如果为偶数，则返回中间结点的任意一个。

（思路：两个指针，同时从头结点出发，一个走一步，一个走两步，走得快的指针到达链尾时，走得慢的指针正好在链表中间）

b. 判断一个单向链表是否构成环形结构。

（思路：同上，两个指针，一快一慢，如果快指针追上了慢指针，则链表成环；如果快指针走到了链尾，则不成环）

代码：

struct ListNode{    int val;    ListNode* next;};ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {    if(pListHead==NULL || k<=0)        return NULL;    ListNode* pAhead=pListHead;    for(unsigned int i=1;i
     
      next!=NULL)            pAhead=pAhead->next;        else            return NULL;    }    ListNode *pBehind=pListHead;    while(pAhead->next!=NULL){        pAhead=pAhead->next;        pBehind=pBehind->next;    }    return pBehind;}
     

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/529d3ae5a407492994ad2a246518148a?rp=1

AC代码：

class Solution {public:    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {    	if(pListHead==NULL || k<=0)            return NULL;        ListNode* pAhead=pListHead;        for(int i=1;i
     
      next!=NULL)                pAhead=pAhead->next;            else                return NULL;        }        ListNode *pBehind=pListHead;        while(pAhead->next!=NULL){            pAhead=pAhead->next;            pBehind=pBehind->next;        }        return pBehind;    }};