找出单链表中的倒数第k个元素

题目

给定一个单链表找到倒数第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;
    }