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

思路一：快慢指针，快指针先走k步（如果长度不够返回null），然后快慢指针一块移动，慢指针指向的就是倒数第k个节点。

import java.util.*;

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ListNode start = pHead;
        while(k>0){
            if(start!=null){
                start=start.next;
            } else{
                return null;
            }
            k--;
        }
        ListNode end = pHead;
        while(start!=null){
            start=start.next;
            end=end.next;
        }
        return end;
    }
}

思路二：使用栈来倒序存储节点，如果栈容量小于k，返回null。连续k次出栈，得到最终结果。

import java.util.*;

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        Stack<ListNode> st = new Stack<>();//申请栈，必须说明类型。
        ListNode cur = pHead;
        while(cur!=null){
            st.push(cur);//入栈操作
            cur=cur.next;
        }
        if (st.size()<k) return null;
        ListNode ans =null;
        while (k-->0){
            ans=st.peek(); //栈顶节点
            st.pop();//出栈
        }
        return ans;
    }
}