剑指offer----链表的倒数第k个节点

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

这个题的难点是几种特殊情况的判定

• head==null
• k < = 0;
• k > 链表的长度

以及对算法的一些简单求解
方法一：

import java.util.*;
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {

    Stack<ListNode> stack = new Stack<ListNode>();
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        if(stack.size() < k || k == 0){
            return null;
        }
       
        for(int i = 0; i < k - 1; i++){
            stack.pop();
        }
        return stack.pop();
    }
}

利用栈的先进后出的特性进行求解。

方法二：

import java.util.*;
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode bHead = head;
        if(head == null || k <= 0){
            return null;
        }
        int first = 0;
        while(first != k){
            if(head == null){
                return null;
            }
            head = head.next;
            first++;
        }
        while(head != null){
            
            head = head.next;
            bHead = bHead.next;
        }
        return bHead;
    }
}

使用两个指针一个指针先向前移动k - 1个节点，然后第二个指针和第一个指针一起移动，当第一个指针走到末尾的时候，第一个指针也就走到了倒数第k个节点了
当以第一个指针到达第k - 1个节点的时候，剩下的节点数为size - k个节点。
倒数第k个几点也就是正数第 size - k个节点， 主要思路就是让一个指针能够从head开始走size - k次就到达了倒数第k个节点了