链表中倒数第K个节点

题目描述

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

做这道题时，由于受之前题目的影响，下意识地想到使用栈、数组之类的来存储链表。

方法一：使用递归，实质上是使用栈

public class Solution {
    int n = 0;
    ListNode res;

    public ListNode FindKthToTail(ListNode head, int k) {
        if (head != null) {
            if (head.next != null)
                FindKthToTail(head.next, k);
        }
        n++;
        if (n == k) {
            res = head;
        }
        return res;
    }
}

方法二：使用数组

public class Solution {
     public static ListNode FindKthToTail(ListNode head,int k) {
         ListNode[] tmp = new ListNode[1000];
         int i;
         for(i = 0; head != null; i++) {
             tmp[i] = head;
             head = head.next;
         }
         return (i - k) < 0 ? head:tmp[i - k];
     }
}

代码都简单易懂，就不解释了。

方法三：

遍历一遍链表得到链表长度n，再遍历一遍链表，第n－k＋1个便为所求。代码略。

虽然上述代码均能完成要求，有的有较好的时间复杂度，有的有较好的空间复杂度，有的两者都有。但是总是感觉怪怪的，不是自己想要的方法。有没有方法在只遍历一次且不需要额外空间的情况下得到答案呢？

方法四：

public class Solution {
    public static ListNode FindKthToTail(ListNode head,int k) {
        ListNode start = head, end = head;
        for(int i = 0; i < k; i++) {
            if(end == null) 
                return null;
            end = end.next;
        }
        while(end != null) {
            start = start.next;
            end = end.next;
        }
        return start;
    }
}

设置两个指针，让end指针与start指针相距为k，这样当end指针遍历到最后时，start指针恰好指到倒数第k个。这样只需要遍历一次，并且不需要额外空间。这才是我们想要的解法！

但是。。。问题真的这么简单吗？

上面的程序看似简单地实现了巧妙的原理，但是实际上却避开了这道题目的三个大坑。
第一坑：输入的head指针为空。由于会涉及到链表head.next操作，那么head就绝对不能为空，否则会报错。

第二坑：链表节点数小于k。仍然会因为访问null.next而报空指针错误。上述程序在end后移的过程中每一步都会判断当前是否为空，是的话直接返回null。

第三坑：输入的参数k为0。若k为无符号整数，循环条件使用的是k-1的话，k-1得到的将不是-1而是4294967295，我们又没有设置每一次均检查是否为空的话，将直接爆掉最后报空指针异常。