描述

输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。

解题思路

将倒数第K个转为正数第index个 时间复杂度为O(n),空间复杂度为O(1)

func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {
    count := 0
    head := pHead
    for head != nil {
        // 计算链表长度
        count++
        head = head.Next
    }
        // 将倒数第k个转为正数第index个
    index := count - k
        // 如果超出链表长度限制
    if index < 0{
        return nil
    }
    for pHead != nil && index > 0 {
        index--
                // 去掉多余的节点
        pHead = pHead.Next
    }
    return pHead
    // write code here
}

快慢指针实现 时间复杂度为O(n),空间复杂度为O(1)

1. 因为是倒数第k个，所以我们先让快指针先走k步
2. 如果fast指针为null,那么说明超过了链表长度限制，返回null
3. 如果fast走了k步，且不为null,那么我们再用慢指针从头节点和快指针一起走，直到快指针为null.返回慢指针

    public ListNode FindKthToTail(ListNode pHead, int k) {
        // 判断链表头是否为空
        if (pHead == null) {
            return null;
        }
        // 将快指针指向头节点
        ListNode fast = pHead;
        int i = 0;
        while (k > i) {
            // 当fast为空表示越界
            if (fast == null){
                return null;
            }
            // 继续向后走
            fast = fast.next;
            i++;
        }
        // 将慢指针指向链表头
        ListNode slow = pHead;
        // 循环结束的条件为快指针走到结尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 返回慢指针
        return slow;
    }

   快慢指针算法图例，以k等于2来举例，链表为1->2->3->4->5