题目：实现一种算法，找出单向链表中倒数第k个节点。返回该节点的值。

Leetcode在线OJ系统：传送门

示例：

graph LR
A[1]-->B[2]
B[2]-->C[3]
C[3]-->D[4]
D[4]-->E[5]
1
2
输入：k = 2
输出：4

说明：给定的 k 保证是有效的。

思路：双指针法。定义两个指针first和second，first指针先走k - 1步，然后second指针和first指针同时走，每次走一步，当first指针到达链表末尾时，second指针指向的节点即为倒数第k个节点。

Java语言实现如下：

单链表节点类定义可查看文章：数据结构之链表-基础知识

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int kthToLast(SinglyLinkedListNode head, int k) {
    if (head == null || k <= 0) {
        return 0;
    }
    SinglyLinkedListNode first = head;
    SinglyLinkedListNode second = head;
    while (k-- > 1) {
        // 长度不足k
        if (first.next == null) {
            return 0;
        }
        first = first.next;
    }
    while (first.next != null) {
        first = first.next;
        second = second.next;
    }
    return second.val
}