前言

我们在写代码的时候要注意鲁棒性。那么所谓的鲁棒性是指程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理。提高代码的鲁棒性的有效途径是进行防御性编程。防御性编程是一种编程习惯，是指预见在什么地方可能会出现问题，并为这些可能出现的问题制定处理方式。

那么在面试时，最简单也是最实用的防御性编程就是在函数入口添加代码以验证用户输入是否符合要求。比如我们常用的输入值的边界值检测和特殊值判断。另外，我们在面对题目的时候，要多问自己几个 “如果不…那么…” 这样的话，比如接下来的这题 “链表中倒数第 k 个节点”，就隐含着的一个条件，如果链表中的节点个数大于 k 呢。那么我们在编写代码的时候就必须把这种情况处理好。

题目(链表中倒数第 k 个节点)

题目:输入一个链表，输出该链表中倒数第 k 个结点。题目从 1 开始计数，头结点为1，以此类推…

算法思路

比较直观的思路就是遍历一遍链表，得到链表的节点个数 n，那么倒数第 k 个节点的位置就在 n-k+1 的位置上，因此需要再次遍历链表。

那么能不能只遍历链表一次呢？可以的。我们可以设置两个指针p1，p2,初始 p1 指向头结点，p2为空。然后，p1 先移动到正向第 k 个节点的位置，然后更新 p2 的指针指向头结点。然后就这样两个指针同时前进，直到前面的 p1 指针指向链表尾节点，此时 p2 所指的节点即为所求。有点类似有个尺子在衡量，然后水平移动尺子，最后尺子的初始位置就是所求。

算法实现

复杂度分析

两个算法思路的时间复杂度都为 O(n)，因为都是线性遍历。但是由于后者只需遍历一遍，因而后者的时间效率更优；空间复杂度为 O(n)

参考

<<剑指offer2>>