题解 | #链表中倒数最后k个结点# 快慢指针/栈/递归

解法1:快慢指针

快指针先走K-1步慢指针再出发，当快指针到结尾的时候时候，慢指针就到了倒数第K个节点

import java.util.*;
public class Solution {

    public ListNode FindKthToTail (ListNode pHead, int k) {
        if (pHead == null || k == 0) {
            return null;
        }
        if (pHead.next == null && k == 1) {
            return pHead;
        }
        if (pHead.next == null && k > 1) {
            return null;
        }
        ListNode slow = pHead;
        ListNode fast = pHead;
        int count = 1;
        while(count < k && fast.next != null) {
            fast = fast.next;
            count++;
        }
        if(count < k){
            return null;
        }

        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;            
        }
        return slow;
    }
}

解法2:借助

全部入栈之后，依次出栈，第k个出来的就是倒数第K个

import java.util.*;
import java.util.*;
public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if (pHead == null || k == 0) {
            return null;
        }
        Stack<ListNode> visited = new Stack<ListNode>();
        while (pHead != null) {
            visited.push(pHead);
            pHead = pHead.next;
        }
        int count = 0;
        ListNode result = null;
        while(!visited.empty() && count < k) {
            result = visited.pop();
            count++;
        }
        if(count < k) {
            return null;
        }
        return result;
    }
}

解法3:递归

import java.util.*;
import java.util.*;
public class Solution {
    int size = 0;
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if (pHead == null || k == 0) {
            return null;
        }
        ListNode node = FindKthToTail(pHead.next, k);
        size++;
        if(size < k) {
            return null;
        } else if (size == k){
            return pHead;
        } else {
            return node;
        }
    }
}

参考牛客的一个帖子得到的办法