解法，我也是从这里学的，博客只是说一下自己的理解

挺有意思的，返回的是倒数的元素，假设是正数的，我们可以从头数，但是倒数的，会不会想把这个单链表翻转一下呢？？还是先遍历链表数好总数然后再数（总数-n个）？ 

其实说白了就是能倒着数n个就行了，有没有想到栈？先进后出？全进了之后开始数N个？进一步的，递归！而且递归能够节省空间啊。

解法二：设置两个指针，控制他们的距离为N，然后先后遍历链表，等前指针遍历到末尾的时候，后指针指向的就是所求节点（五体投地）

描述：

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

思路：

双指针，p1先走k步，然后同时走，p1到头时候返回p2

倒数第k个就是正数第n-k+1个，从第一个结点到第n-k+1个结点一共要走n-k步，从第k+1个结点到n+1个结点也是n-k步，从第一个结点到第k+1个结点，走k步

代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if not head:
            return None
        p1 = head
        p2 = head
        l = k
        while l > 0:
            try:
                p1 = p1.next
                l -= 1
            except:
                return None
        while p1:
            p1 = p1.next
            p2 = p2.next
        return p2

结果：

运行时间：26ms

占用内存：5848k

这题就一个思路问题，想到了就容易，想不到就感觉很难，容易从超高时间复杂的角度来考虑问题。

思路：倒数第K个节点，其实也就是正数第Length-k+1个节点。

因此，两个指针就完事了，一个先不动，另一个指针先跑k-1步（注意：此时，第一个指针跑了k-1，其实此时这个指针距离第二个指针为k），然后，两个指针同时往后跑就行了，他们的距离为k，直到前面的指针跑到末尾，另一个指针指向的就是倒数第K个节点。

代码：
public static int getDaoShuK(int k,LinkNode pre,LinkNode behind) {
		for(int i=0;i<k-1;i++) {
			pre=pre.next;
		}
		while(pre.next!=null) {
			pre=pre.next;
			behind=behind.next;
		}
		return behind.value;
	}```

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

为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1，2，3，4，5，6。这个链表的倒数第3个结点是值为4的结点。

练习地址
实现
倒数第k，正数n-k+1

方法：遍历一次，避免计算长度

两个指针p1,p2，保持k-1的距离，p1走到尾，p2为倒数k
/** 21 链表中倒数第K个节点*/
public class C22_list_FindTailK {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    //倒数第k，正数n-k+1
    //遍历一次,两个指针p1,p2，保持k-1的距离，p1走到尾，p2为倒数k
    public static ListNode tailK(ListNode head, int k) {
        if (head == null || k == 0) { return null; }
        ListNode p1 = head;
        ListNode p2 = null;
        for(int i =0;i<k-1;i++){ //a指针先走k-1
            if(p1.next!=null){
                p1=p1.next;
            }else {
                return null;
            }
        }
        p2=head;
        while (p1.next!=null){//a,b同时走
            p1=p1.next;  //a走到尾
            p2=p2.next;  //b为倒数第K个
        }
        return p2;
    }
}

Test
 public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(5);
        ListNode node3 = new ListNode(7);
        node1.next = node2;
        node2.next = node3;
        System.out.println(tailK(node1,1).val);

    }

实现
20210203

// 遍历了2遍，不推荐
//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的
//用户内存消耗：36.3 MB, 在所有 Java 提交中击败了34.39%的用户
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head==null || k<=0) return null;
        ListNode node = head;
        int n =0;
        while(node!=null){
            n++;
            node =node.next;
        }
        for(int i=1;i<n-k+1;i++){
            head=head.next;
        }
        return head;

    }
}