剑指offer--链表中倒数第k个结点（双指针一次遍历，代码鲁棒性，类似问题）_综合

题目描述：
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

分析：
链表中的倒数第k个结点，我们很容易想到先遍历到链表的尾部，然后向前回溯k个结点，但这需要双向链表才能完成，题目中的链表很显然是单向的。倒数的第k个结点也是正数第n-k+1个结点，我们从头遍历到尾获得链表总结点个数n，然后再一次从头遍历到第n-k+1个结点即可，可这需要两次遍历。我们想一想有没有更好的方法，只需要遍历一次就可以得到我们想要的结果。

我们先让一个指针从头开始走 k-1步，当第一个指针走完k-1步时，它距离尾结点的距离和倒数第k个结点距离头结点的距离相等，（因为倒数第k个结点距离尾结点 k-1步，而现在指针1距离头结点k-1步），此时再让一个新的指针开始从头走，当第一个指针走到尾结点时，第二个指针刚好走到倒数第k个结点的位置。
在这里插入图片描述
根据上面的分析，我们很快能写出代码：

 ListNode* getKthFromEnd(ListNode* head, unsigned int k) {
    ListNode* pAhead = head;ListNode* pBhead = NULL;for(int i = 0 ; i < k - 1; i++){
    if(pAhead->next != NULL)pAhead = pAhead->next;}pBhead = head;while(pAhead->next != NULL){
    pAhead = pAhead->next;pBhead = pBhead->next;}return pBhead;}

但是面试官看到了这样的代码并不会满意，因为我们得代码不够鲁棒，以上面的代码为例，面试官可以找出三种办法让程序崩溃。
(1)输入的head为空指针。由于代码会试图访问空指针指向的内存，从而造成程序崩溃。
(2)输入的以head为头节点的链表的节点总数少于k。由于在for循环中会在链表上向前走k-1步，仍然会由于空指针而造成程序崩溃。
(3)输入的参数k为0。由于k是一个无符号整数，那么在for循环中k-1得到的将不是-1，而是4294967295(无符号的OxFFFFFFFF)。因此，for循环执行的次数远远超出我们的预计，同样也会造成程序崩溃。

对代码进行修改：

  ListNode* getKthFromEnd(ListNode* head, unsigned int k) {
    if(head  == NULL || k == 0)return NULL;ListNode* pAhead = head;ListNode* pBhead = NULL;for(int i = 0 ; i < k - 1; i++){
    if(pAhead->next != NULL)pAhead = pAhead->next;elsereturn NULL;}pBhead = head;while(pAhead->next != NULL){
    pAhead = pAhead->next;pBhead = pBhead->next;}return pBhead;}

类似题目：
求链表的中间节点。如果链表中的节点总数为奇数，则返回中间节点；如果节点总数是偶数，则返回中间两个节点的任意一个。为了解决这个问题，我们也可以定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。

ps：当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些(比如一次在链表上走两步)，或者让它先在链表上走若干步。