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

输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

首先我们清楚，链表是由其头节点决定的，所以问题转化为输入一个头节点，输出一个头节点。所以我们只需要输出倒数第k个节点即可

方法1 常规一个循环解决
先求出链表长度，一个遍历就可以找到该节点。
时间复杂度 O(n)
空间复杂度 O(1)

import java.util.*;

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if(pHead == null){
            return null;
        }
        int length = 0;
        ListNode node = pHead;
        while(node.next != null){
            node = node.next;
            length++;
        }
        if(k > length+1){
            return null;
        }
        ListNode pre = pHead;
        for(int i=0; i<length-k+1; i++){
            pre = pre.next;
        }
        return pre;
    }
}

方法2 双指针法
用指针pre先移动k个节点，之后两个指针同时移动，当pre指针移到链表末尾时，ref指针刚好移动到倒数第k个节点，输出ref指针即可。
时间复杂度 O(n)
空间复杂度 O(1)

import java.util.*;

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