题目描述

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

解题思路

1，硬解，先求出链表总长度，然后倒数第k个就是正数第count-k+1个
2，软解，双指针，两个同时开始走，p指针先跑，并且记录节点数，当p指针跑了k-1个节点后，pre指针开始跑， 当p指针跑到最后时，pre所指指针就是倒数第k个节点，也就是说两个指针之间相差k-1，一个到最后，另一个刚好到k

代码实现

/** * */
package 链表;

/** * <p> * Title:FindKthToTail * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月22日 下午2:32:24 */
public class FindKthToTail {
    public ListNode NodeFindKthToTail(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        int count = 1;
        ListNode p = head;
        while (p.next != null) {
            p = p.next;
            count++;
        }
        if (k > count || k < 1) {
            return null;
        }
        p=head;
        int curcount =1;
        while(curcount<count-k+1&&p.next!=null){
            p=p.next;
            curcount++;
        }
        return p;

    }
    //========================================================优化
    public ListNode NodeFindKthToTailSuper(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        if ( k < 1) {
            return null;
        }
        ListNode p = head;
        for (int i = 1; i < k; i++) {
            if(p.next!=null)
               p = p.next;
            else
                return null;   //用来控制k的长度，防止k的长度超过了总长
        }         //p到达了指定位置
        ListNode pre = head;
        while(p.next!=null){
            p=p.next;
            pre = pre.next;    //p和pre同时出发
        }
        return pre;


    }

}