题目
前面几个题目考察的是考虑问题的全面性，接下来看几个考察代码健壮性的面试题。
所谓健壮性也叫鲁棒性（Robust），其核心要素是即使输入不符合要求的参数，也不至于让程序崩溃，也就是对各种异常和边界的处理。提高代码健壮性的有效方式是防御性编程，比如对参数的校验，对于不符合要求的参数予以返回或抛出异常处理。
下面我们来看今天的题目：
输入一个链表，输出该链表中倒数第 k 个结点。
为了符合大多数人的习惯，本题约定从 1 开始计数，即链表的尾结点是倒数第 1 个结点。例如一个链表有 6 个结点，从头结点开始它们的值依次是 1、2、3、4、5、6，那么这个链表的倒数第 3 个结点是值为 4 的结点。
解题思路
这个题目要分两种情况来看：
- 如果是双向链表，就比较简单了，因为双向链表每个结点有两个指针，一个指向前驱结点，一个指向后驱结点，倒数第
k个结点只需要从尾结点往前移动指针即可。 - 如果是单向链表，就要复杂一些，因为没有前驱结点，我们需要先遍历一遍链表获取所有结点数
n，计算出倒数第k个结点的位置：n - k + 1，然后根据这个位置再次遍历链表，获取对应结点。
上述这种做法是没有问题的，但是遍历两次链表时间复杂度是 O(2n)，我们可不可以对这个操作流程进行优化，通过 O(n) 即遍历一次链表就能获取到指定结点呢，大家可以先思考下。
答案是可以，这需要两个指针来实现，初始时两个指针都指向头结点，我们要保证两个指针的间距保持在 k-1，这样，当一个指针到达尾结点时，另一个指针刚好到达倒数第 k 个结点的位置。
为了实现这个目标，我们先让第一个指针往前走 k-1 步，第二个指针保持不动，接着从第 k 步开始，第二个指针也往前移动，这样一来两个指针就始终保持在 k-1 的距离，直到第一个指针到达尾结点，这个时候第二个指针指向的位置就是倒数第 k 个结点，并且整体下来的时间复杂度是第一个指针遍历了整个链表，时间复杂度是 O(n)。
有了以上思路代码实现起来就比较简单了，需要注意的是我们需要关注代码的鲁棒性，对输入参数要进行必要的校验，以免空指针异常。
实现代码
接下来，我们来编写对应的实现代码。
单链表结点类在 O(1) 时间内删除单链表结点这篇教程中已经定义过：
// Node 单链表结点类
type Node struct {
data interface{}
next *Node
}
时间复杂度为 O(2n) 的实现代码如下：
// 版本1：时间复杂度为 O(2n) 的实现
func findKthNodeToTailV1(head *Node, k int) (*Node, error) {
// 参数无效
if head == nil || head.next == nil || k <= 0 {
return nil, errors.New("invalid params")
}
// 第一次遍历
node := head
n := 1
for node.next != nil {
n++
node = node.next
}
// k 大于链表长度
if k > n {
return nil, errors.New("k is longer than linked_list length")
}
// k 和链表长度相等，则倒数第 k 个结点正好是头结点
if k == n {
return head, nil
}
// 其他情况需要从链表头部开始第二次遍历，拿到顺序第 n - k + 1 个结点返回
target := n - k + 1
n = 1
node = head.next
for node.next != nil {
n++
if n == target {
return node, nil
}
node = node.next
}
return nil, errors.New("node not found")
}
下面是时间复杂度为 O(n) 的实现代码：
// 版本2：时间复杂度为 O(n) 的实现
func findKthNodeToTailV2(head *Node, k int) (*Node, error) {
// 参数无效
if head == nil || head.next == nil || k <= 0 {
return nil, errors.New("invalid params")
}
// 初始化两个指针
aP := head
bP := head
// 只将 a 指针移动 k - 1
for i := 0; i < k - 1; i++ {
aP = aP.next
// 到达链表尾结点，表明 k 大于链表长度
if aP == nil {
return nil, errors.New("k is longer than linked_list length")
}
}
// 同时移动 a、b 指针，直到 a 到达链表尾结点
for aP.next != nil {
aP = aP.next
bP = bP.next
}
// 返回 b 指针对应的结点，就是链表倒数第 k 个结点
return bP, nil
}
最后编写链表初始化和测试代码如下：
func main() {
// 初始化单链表
head := &Node{
data: 1,
} // 头结点
prev := head // 记录上一个结点
for i := 2; i <= 6; i++ {
node := &Node{
data: i,
}
prev.next = node
prev = node
}
// 测试代码
// v1
k := 3
h1 := head
kNodeV1, err := findKthNodeToTailV1(h1, k)
if err != nil {
fmt.Println(err)
return
}
fmt.Printf("单链表倒数第 %d 个结点v1: %#v\n", k, kNodeV1)
// v2
h2 := head
kNodeV2, err := findKthNodeToTailV1(h2, k)
if err != nil {
fmt.Println(err)
return
}
fmt.Printf("单链表倒数第 %d 个结点v2: %#v\n", k, kNodeV2)
}
执行代码，打印结果如下，表示代码测试通过：
