链表中倒数第K个节点

1.题目
输入一个链表，输出该链表中倒数第k个结点。
如，输入：1,{1,2,3,4,5}；返回：{5}
2.思路
方法一：我首先想到的是存入hashmap，然后直接对应键值来取值，由于是倒数的，所以要有长度记录
从0开始储存，记录长度为len，则找倒数第k个就是(len-k)个
时间复杂度：O(n),空间复杂度：O(n)

import java.util.*;
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        HashMap<Integer,ListNode> map=new HashMap<>();
        int len=0;//起始位置
        while(head!=null){
            map.put(len,head);
            head=head.next;
            ++len;//记录链表长度
        }
        return map.get(len-k);
    }
}

方法二：快慢指针
快指针先走 k-1 步，到达第 k 个节点。
然后两指针同时齐步走，当快指针到达末尾时，慢指针在倒数第 k 个节点上。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        int index=k;
        int count=0;//记录链表长度
        ListNode fast=head;//快指针
        ListNode slow=head;//慢指针
        while(fast!=null){
            fast=fast.next;
            count++;
            if(index<1){
                slow=slow.next;
            }
            --index;
        }
        if(k>count) return null;//如果目标位置大于链表长度
        return slow;
    }
}