目录

1. 链表中倒数第 k 个节点 

1.1 题目描述

1.2 思路一

 1.3 思路二：

 1.4 总结----代码的鲁棒性

1. 链表中倒数第 k 个节点 

原题链接：

剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode）https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

1.1 题目描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

1.2 思路一

题目求的是链表的倒数第 k 个节点，根据题目得知这是一个单向链表，我们无法从后往前找到链表的倒数第 k 个节点，于是我们会想到从前往后去找倒数第 k 个节点。但是我们不知道倒数第 k 个节点前面有多少个节点。于是，我们很自然地想到先求出链表的节点个数 count，然后就求出了倒数第 k 个节点前有 count - k 个节点，然后我们再用一个指针去遍历找到倒数第 k 个节点就可以啦。

struct ListNode* getKthFromEnd(struct ListNode* head, int k) {//对输入进行判断，提高代码的鲁棒性(健壮性)if (head == NULL || k <= 0){return NULL;}//用cur指针遍历链表统计节点个数struct ListNode* cur = head;int count = 0;while (cur != NULL){count++;cur = cur->next;}//对输入进行判断，提高代码的鲁棒性    if (k > count){return NULL;}//找到倒数第k个节点struct ListNode* ret = head;int i;for (i = 1; i < count - k + 1; i++){ret = ret->next;}return ret;
}

 1.3 思路二：

遍历两次链表还是太麻烦了，能不能只遍历一次链表就找到结果呢？答案是肯定的，我们可以维护两个指针slow，fast，将他们均初始化为头结点 head。然后让 slow 指针先不动，让 fast 指针先向后走k-1步，此时slow与fast之间就隔了 k - 1 个节点，然后保持slow与fast之间的距离始终为 k - 1个节点，即之后让 slow 与 fast 同时向后移动。直到 fast 指向尾节点，此时 slow 就指向了链表的倒数第 k 个节点。

下面以链表 1->2->3->4->5->NULL ，k = 3，举例分析：

struct ListNode* getKthFromEnd(struct ListNode* head, int k){//对输入进行判断，提高代码的鲁棒性(健壮性)if(head == NULL && k <= 0){return NULL;}//两个指针的初始化struct ListNode* slow = head, *fast = head;//快指针先走走k-1步，此情况中可能超过快指针可走的步数，//此时表明链表的节点个数小于k的值，返回NULLint i = 0;for(i = 0;i < k - 1;i++){if(fast != NULL)fast = fast->next;elsereturn NULL;}//让慢指针与快指针同时走，直到快指针走到尾节点//最后慢指针指向的节点就是倒数第k个节点while(fast->next != NULL){slow = slow->next;fast = fast->next;}return slow;
}

 1.4 总结----代码的鲁棒性

鲁棒性是英文Robust的英译，有时也翻译成健壮性。所谓的鲁棒性是值程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理。

对于本题而言对于鲁棒性应做如下考虑：

(1)：输入的head指针为空指针的情况。

(2)：链表的节点数小于k的值。

(3)：k为非正数的情况。