【图文解析】链表中倒数第 k 个结点
例题描述
输入一个链表，输出该链表中倒数第k个结点。
示例：
- 输入：
1->2->4->1->3->4，k =3 - 输出：此列表中的结点
1（序列化形式：[1,3,4]）
结点结构体定义
struct ListNode {
int val;
struct ListNode *next;
};
解题思路
-
前后指针法：
建立一个前指针front，再建立一个后指针back。让前指针先向后走给定的k步，然后两指针开始同时步进。
所以当前指针走到链表尾部时，后指针此时位于链表的倒数第k个结点处。
-
判断创建前后指针，将他们都初始化指向为链表的头指针
pHead。 -
建立一个计数器，计数因子变量
i，初始化为0。然后开始循环遍历，进行步进前指针。判定条件为前指针不为空（NULL），如果为空说明到达了链表尾部，满足循环跳出条件而退出。
这里循环条件还要加上一句i < k，与前指针不为空的条件构成逻辑与的关系，共同控制循环。因为如果给定的链表结点个数小于给定值，循环中前指针就会走到NULL，再进行下一次循环时就会发生对空指针解引用的操作，程序出现错误。 -
循环退出条件：①前指针不满足条件
i < k，此时完成了步进k步的任务，此时可以开始同时步进。②前指针不满足条件front != NULL，此时前指针还没有步进k步就到达了链表尾部，说明< 链表结点数并没达到k个，用户给定的k值过大 >，此时我们通过if语句进行筛选。
< 如果 > ：计数因子i小于给定的k值，说明链表没有那么多的结点，不存在倒数第k个结点，此时返回空。
< 否则 > ：计数因子i等于(或大于)给定的k值，说明完成了步进k个单位的任务，下面可以开始共同步进逻辑。 -
因为前指针总位于后指针的“后边某个结点”，所以不必进行有效性判定，因为如果前指针都无效了，那么后指针就不会继续运动了，只需前指针作为循环判定条件，判定其有效性即可。
-
如果前指针不为空，说明没有到达表尾，此时使前指针向后走一步，后指针也同样步进
1，都走完一步之后进行下一次循环。 -
当且仅当前指针到达
NULL，此时慢指针back即为此链表的倒数第k个结点。返回后指针即可。
代码实现
ListNode* FindKthToTail(ListNode* pHead, unsigned int k) {
ListNode *front = pHead;
ListNode *back = pHead;
int i = 0;
for(;front != NULL && i < k;front = front->next)
i++;
//如果等于k说明链表有k那么长的长度，没有说明链表不足k的长度，不存在倒数k的结点，返回空
if(i < k){
return NULL;
}
while(front != NULL){
front = front->next;
back = back->next;
}
return back;
}
小结
程序中前指针front的循环判定条件十分严苛，不仅仅是前指针不为空即可，还需要考虑给定k值过大的情景，所以在做数据结构相关题目时一定要考虑全面，例如传参为空链表、链表只有单结点、给定参数过大等等情况，我们所编写的代码一定要有处理这类错误的能力。