题目
给定一个单链表找到倒数第k个元素 ，无环
解
题目中的关键点
单链表 （没有长度）
- 如果知道单链表的长度len，则倒数第k个元素，就可以遍历链表到len-k个位置即可 ，但是要获得长度，必须先遍历一遍链表
- 如果我们不知道链表长度，如何解？
- 假如有两个指针一个快一个慢，快和慢之间的距离为k，就是从链表尾到倒数第k个节点的距离，当快的指针走链表尾部，这时候慢指针是不是就是指向倒数第k个节点
- 假如快指针为p1，慢指针为p2 ，p1 先沿着链表头部走到第k个位置，此时p2开始前行，每次前进一步，当p1==null时，快指针走到了链表尾部，此时p2的位置就是倒数第k个节点
时间复杂度O(n)
执行顺序图
tcp-链表倒数第k个元素.png
链表节点简单结构
public class Node<T> {
public Node next;
public T data;
public Node(T data) {
this.data = data;
}
}
算法实现
public static Node<Integer> findK(Node<Integer> head, int k) {
Node<Integer> p1 = head;
Node<Integer> p2 = head;
int index = 0;
while (p1 != null) {
p1 = p1.next;
if (index == k){
p2 = p2.next;
}else {
index++;
}
}
return p2;
}
