在单链表中如何获得倒数第K个结点，最直接的方式，设置一个计数器，遍历完整个链表，获得链表的长度，然后计算获得倒数第k个结点。
但是上述方式，遍历链表2遍，效率并不好。如何一次获得结果？设置 a，b 两个指针，起始都指向头结点，然后让 a 指针先遍历 k-1 个结点，然后 a 和 b 同时遍历链表，当 a 遍历完链表时， b 指向的就是倒数第k个结点。
public class E3 {
static class Node {
int data;
Node next;
}
/**
* 尾插法获得一个带头结点的单链表
* @return
*/
private static Node createLink() {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入结点个数");
int n = scanner.nextInt();
Node head = new Node();
head.next = null;
Node rear = head;
while (n-- > 0) {
Node node = new Node();
node.data = scanner.nextInt();
node.next = null;
rear.next = node;
rear = node;
}
return head;
}
/**
* 在单链表中查找倒数第k个结点
* @param k
* @return
*/
private static int getKNode(Node l, int k) {
//此时a，b均在头结点的位置
Node a = l;
Node b = l;
for (int i = 0; i < k - 1; i++) {
if (a != null) {
a = a.next;
}
else {
throw new RuntimeException("K是一个非法值");
}
}
while (a.next != null) {
a = a.next;
b = b.next;
}
return b.data;
}
public static void main(String[] args) {
//创建长度为5的链表
Node link = createLink();
int value = getKNode(link, 3);
System.out.println(value);
}
}
=========
结果
请输入结点个数
5
---------------
1
2
3
4
5
----------------
3
