输入一个链表,输出该链表中倒数第k 个结点。为了符合大多数人的习惯,本题从1 开始计数,即链表的尾结点是倒数第1 个结点.例如一个链表有6 个结点,从头结点开始它们的值依次是1 、2、3、4、5 、6。这个个链表的倒数第3 个结点是值为4 的结点。
需要注意边界问题
public class Node {
public int value;
public Node next;
}
pubic void test(Node head, int k) {
if (head == null || k <= 0) {
return null;
}
Node pointer = head;
// 1. 将头节点移动到k位置.
for (int i = 1; i < k; i++) {
if (head.next != null) {
// 每次移动结束后, 节点位置为i+1, 所以移动k-1次,
// 节点是被移动到k位置.
head = head.next;
} else {
return null;
}
}
// 2. 接下来pointer与header同时开始移动, header与pointer始终
// 保持k-1的距离
while (head.next != null) {
head = head.next;
pointer = pointer.next;
}
// 3. 移动结束, pointer节点为目标节点
return pointer;
}
网友评论