链表中倒数第k个结点

略

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

分析

初见

  对于一个单向链表，如果要实现查找倒数的第k个结点，就需要在遍历链表时记录每个位置的值，到达最后一个值后，再倒着推出倒数第k个结点，但是如果要一一记录每个值需要更多的空间，有没有一个更好的方法呢。

  可以用两个指针，一个指针先向后遍历，当遍历了k个结点时，第二个指针跟随着第一个指针一一向后移动，由于第一个指针先遍历的，所以他会先到达结尾，当它到达结尾时，第二个移动的指针就是需要的倒数第k个结点。

public class Solution {
	public ListNode FindKthToTail(ListNode head,int k) {

        ListNode pre=head;
        ListNode last=head;       
        for(int i=1;i<k;i++){
           pre=pre.next;
        }
        while(pre.next!=null){
            pre = pre.next;
            last = last.next;
        }
        return last;
    }
}

为了代码的鲁棒性

  对于代码的鲁棒性，我们需要考虑的是：当链表的头指针为空时（链表为空）；当链表结点总数小于k时（倒数到链表外了）；当倒数第0个结点时（由于倒数是从1开始的）。这三个都需要考虑到是否会导致程序崩溃。

代码实现

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
	public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null||k<=0){//链表为空或出现倒数为负数的情况
            return null;
        }
        ListNode pre=head;
        ListNode last=head;       
        for(int i=1;i<k;i++){
            if(pre.next!=null){//如果第一个指针遍历完，第二个还没出发
                pre=pre.next;	//说明k大于链表结点总数
            }else{
                return null;
            }
        }
        while(pre.next!=null){
            pre = pre.next;
            last=last.next;
        }
        return last;
    }
}

总结

1. 对链表的理解，单向链表遍历只能从头到尾的特点。
2. 代码的鲁棒性，鲁棒英文为Robust，也可翻译为健壮性，就是对不合要求的输入予以合理的处理，比如要求输入的账户名为数字串，实际如果输入了字符，代码健壮的程序应该给出提示信息。