题解 | #链表中倒数最后k个结点#

思路，倒数K个，第一个想到的就是栈，一个一个入栈，最后取K个。进阶要求空间复杂度为1，栈的空间复杂度为n，那就使用递归，链表有个好处，倒排的时候不用考虑next，取到的值的next还在

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = pHead;
        while(cur!=null){stack.push(cur);cur=cur.next;}
        int count=0;
        ListNode head =null;
        while(count++<k){
            if(stack.empty())return null;
            head = stack.pop();
        }
        return head;
    }
}

• 递归 ,解释一下else return node;这行代码，原则是不会出现，只有当k<=0时才会出现，但是那会node的值就是null，所以也是正确的。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    int size = 0;
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead==null) return null;
        ListNode node = FindKthToTail(pHead.next,k);
        size++;
        if(size<k)return null;
        else if(size == k)return pHead;
        else return node;
    }
}