遍历一次单链表找到倒数第k个结点
该题源自于CC150一书中，题目经典，方法巧妙，书中描述方法大概思路是快行指针法，两个指针保持距离为k遍历链表，当快指针走到链表尾时， 慢指针自然指向倒数第k个结点。
注意边界与间距的控制
Java代码参考
public class LastOfK {
/**
* 找到单链表的倒数第k个结点： 快行指针方法，两个指针保持距离为k遍历链表，
* 当快指针走到链表尾时， 慢指针自然指向倒数第k个结点，注意边界的控制
*
* @param args
*/
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5 };
Node head = new Node(0);// 头结点，哑元
// 单链表的生成
Node p = head;
for (int i = 0; i < arr.length; i++) {
p.next = new Node(arr[i]);
p = p.next;
}
int k = 1;//模拟倒数第k个
Node ans = lastOfK(head, k);
if (ans == null)
System.out.println("null");
else
System.out.println(ans.value);
}
private static Node lastOfK(Node head, int k) {
if (k <= 0 || head == null)
return null;
Node p1 = head.next;
Node p2 = head.next;
int count = 0;
while (p2 != null && count < k) {// 与p1相差k
p2 = p2.next;
count++;
}
if (count < k)// 结点数少于k个
return null;
while (p2 != null) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
private static class Node {
int value;
Node next;
public Node(int value) {
super();
this.value = value;
}
}
}
