链表中倒数第K个节点.md

题目描述

输入一个链表，输出该链表中倒数第k个结点。

节点定义如下：

public class ListNode {
    int val;
    ListNode next = null;
}

测试用例

• 功能测试（第k个节点在链表的中间；第k个节点是链表的头结点；第k个节点是链表的尾结点）
• 特殊输入测试（链表头结点为空指针；链表的节点总数少于k；k=0）

题目考点

• 考查应聘者对链表的理解。
• 考查应聘者所写代码的鲁棒性。

解题思路

假设整个链表有n个节点，那么倒数第k个节点就是从头开始的第n-k+1个节点。

我们定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1步，当第一个指针到达链表的尾节点时，第二个指针正好指向倒数第k个节点。

但是为了保持程序的鲁棒性，需要考虑下面三个问题：

1. 输入头节点为空指针
2. 链表的节点总数少于k
3. 输入k为0

自己解题

/**
 * 链表中的倒数第K个节点
 * @Author rex
 * 2018/7/26
 */
public class Solution {
    /**
     * 自己解法
     * @param head
     * @param k
     * @return
     */
    public ListNode findKthToTail(ListNode head, int k) {
        // 防止空指针和k=0无意义
        if (head == null || k == 0) {
            return null;
        }
        // 第一个指针的步数
        int i = 0;
        ListNode firstNode = head;
        ListNode secondNode = head;
        while (firstNode.next != null) {
            firstNode = firstNode.next;
            i++;
            if (i > k-1) {
                // 保持两个指针距离为k-1
                secondNode = secondNode.next;
            }
        }
        // 还没走到k-1步就结束了
        // 表示链表的节点总数少于k
        if (i<k-1) {
            return null;
        }
        return secondNode;
    }
}

参考解题

同自己解题，只要按照解题思路写出代码，复杂度都是O(N)

补充

鲁棒性是指程序能够判断输入是或否合乎规范要求，并对不符合要求的输入予以合理的处理。

容错性 是鲁棒性的一个重要体现。

提高代码的鲁棒性的有效途径是进行防御性编程，防御性编程是一种编程习惯，是指预见在什么地方可能会出现问题，并为这些可能出现的问题制定处理方式。

对于链表的倒数第K个节点都有固定的解法：两个指针，利用 k + (n-(k-1)) = n-1

解题思路

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