链表中倒数第k个结点

有三种方法：

• 快慢指针解法
  倒数第k个节点，其实就是正数第n-k+1个节点。
  快指针先从head处往前走k-1步，慢指针全程不动，这样快指针走完k-1步后，它们的距离是k-1。
  当快指针走到链表最后一个元素时，二者停下。此时快指针总共走了n步，而慢指针跟它的距离还是k-1。所以慢指针走了n-(k-1)步，即n-k+1步。

public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode first = head;
    ListNode second = head;
    //第一个指针先走k步
    while (k-- > 0) {
        first = first.next;
    }
    //然后两个指针在同时前进
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    return second;
}

• 栈解决
  这题要的是返回后面的k个节点，我们只要把原链表的结点全部压栈，然后再把栈中最上面的k个节点出栈即可。

  class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        Stack<ListNode> stack = new Stack<>();
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        ListNode temp = null;
        while(k-- > 0){
            temp = stack.pop();
        }
        return temp;
    }
  }

  
  
• 递归解决
  
  直接看代码就能懂

  public class Solution {
    int size;
    public ListNode FindKthToTail(ListNode head,int k) {
        //当空节点直接返回
        if(head == null)
            return head;
        //先递  往下传递
        ListNode node = FindKthToTail(head.next, k);
        //当往后返回时计算是k个时，直接返回当前head
        if(++size == k)
            return head;
        //再归 向上返回
        return node;
    }
  }