【38】求链表倒数第k个结点

题目：输入一个单向链表（只有指向下一个结点指针），输出链表中的倒数第k个结点。

分析：

1. 一个单向链表只有指向下一个结点的指针，所以我们无法得到前面一个结点的指针，所以不能通过最朴素的枚举法来求出。

2. 现在要求出倒数第k个结点。现在用一个指针枚举是无法求出，但是我们可以使用两个指针法（非常重要）。

   初始化设置两个指针p1和p2，p1和p2都指向链表的头结点。我们可以先让指针p1指针先走到第k个结点，下一步开始两个指针p1和p2一起走，当p1指向链表最后一个结点的时候p2指向即为倒数第k个结点。

   为什么呢这个方法是正确的？

   当p1指向第k个结点的时候，p2和p1相差k个结点，所以当p1指向尾结点的时候，p2指向的即为倒数第k个结点。

代码：

//链表结点
struct ListNode{
    int value;
    ListNode *nextNode;
}; 

//求倒数第k个结点
ListNode* GetKthFromTail(ListNode *headNode, int k){
    //数据不合法
	if((headNode == NULL) || (k <= 0)){
	    return NULL;
    }
    ListNode *p1 = headNode;
    ListNode *p2 = headNode;
    int count = 1;
    //让p1先走到第k个结点
	while((count < k) && (p1 != NULL)){
        p1 = p1->nextNode;
        ++count;
	}
	//判断数据合法性
	if(p1 == NULL){
        return NULL;
	}
	//两个指针一起走，当p1指向尾结点是p2指向即为倒数第k个结点
	while(((p1->nextNode) != NULL)){
        p1 = p1->nextNode;
        p2 = p2->nextNode;
	}
	return p2;
}