单链表中倒数第K个结点

链表结点定义如下：

typedef int ElemType;

typedef struct Node {
	ElemType data; 
	struct Node *next;
}HeadList;

为了得到倒数第k个结点，很自然的想法是先走到链表的尾部，再从尾部回溯k步。而题中所给的链表结点定义可以看出是单向链表，没有从后往前的指针，因此这种思路是行不通的。

既然不能从尾部回溯，我们可以把思路回到头结点上。
假设整个链表有n个结点，那么倒数第k个结点就是从头结点开始的第n-k+1个结点。如果我们能够得到链表中的结点个数，那么只要从头结点开始往后走n-k+1步就可以了。而链表的长度n只需向后遍历一遍即可得到。
也就是说，这个思路需要遍历两次链表：第一次统计出结点的个数，第二次找第n-k+1个结点。

下面介绍只需要一次遍历的思路：
为了实现这个思路，我们可以定义两个指针，第一个指针从头结点开始向前走k-1步，第二个指针在头结点不动；
此时两个指针之间的结点有k-1个。而倒数第k个结点和尾部结点之间的结点也是k-1个。
然后我们让两个指针一起向前走，让他们之间的距离保持k-1个结点。
当第一个指针走到尾部结点时，第二个指针恰好指向倒数第k个结点。
下面以在有6个结点的链表中找倒数第3个结点为例分析这种思路的过程。

首先用第一个指针从头结点开始向前走2步（k=3)，P1走到第三个结点，如上图a步所示；

接着把第二个指针初始化指向链表的第一个结点，如上图b步所示；

最后让两个指针同时向前遍历，当P1到达链表尾部结点时，P2指针指向的刚好就是倒数第3个结点，如上图c步所示。
上述思路的参考代码示例：

HeadList* FindKthToTail(HeadList* head, int k)
{
	HeadList* p1 = head;
	for (int i = 0; i < k - 1; i++)
	{
		p1 = p1->next;
	}
	HeadList* p2 = head;
	while (p1->next)
	{
		p1 = p1->next;
		p2 = p2->next;
	}
	return p2;
}

上述的代码示例存在三个潜在的风险：

1. 传入的头结点指针为NULL时，会引发非法访问
2. 当传入的实参k值小于0时会返回头结点，而头结点是不存数据的
3. 当传入的实参k值大于链表结点个数，在for循环里会参数对空指针解引用的错误

改进代码示例：

HeadList* FindKthToTail(HeadList* head, int k)
{
	if (head == NULL || k <= 0) return NULL;

	HeadList* p1 = head;
	for (int i = 0; i < k - 1 && p1; i++)
	{
		p1 = p1->next;
	}
	if ( p1 == NULL || p1->next == NULL ) return NULL;
	HeadList* p2 = head;
	while (p1->next)
	{
		p1 = p1->next;
		p2 = p2->next;
	}
	return p2;
}

改进的第一步，就是先对传入的实参检测是否合法，杜绝可能会让程序返回值出错或程序崩溃的错误。
然后就是for循环里加的循环条件，可以防止出现对空指针解引用。
程序中，if ( p1 == NULL || p1->next == NULL ) return NULL; 这句语句的作用就是防止k的值大于链表结点的个数。

测试代码的结构头文件及实现来自：带头结点单链表的C语言代码实现