剑指Offer - PHP链表中倒数第k个节点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
分析
假如有一把尺子，长度为2（即k）。我们将尺子往链表右边挪，当尺子的最右边到达链表的尾部时，尺子的最左边就刚好是倒数第k个节点。
- 使用两个指针，来定义尺子的最左边和最右边。最左边为
$pre，最右边为$behind。 - 挪动尺子，即同时移动两个指针，直到
$behind到达链表尾。 - 返回从
$pre开始的到最后的链表。
代码
<?php
/*class ListNode{
var $val;
var $next = NULL;
function __construct($x){
$this->val = $x;
}
}*/
function FindKthToTail($head, $k)
{
if(empty($head) || $k == 0) return false;
$pre = $behind = $head; // 先初始化，指向头节点 $head
// $behind 先移动，生成长度为 k 的距离（即尺子）
for($i=0;$i<$k-1;$i++) {
if($behind->next == NULL) return false; // 链表中没有足够的 k 个节点
$behind = $behind->next;
}
// 同时挪动两个指针，即挪动尺子
while($behind->next != NULL) {
$pre = $pre->next;
$behind = $behind->next;
}
return $pre; // 返回链表
}
关于 LearnKu
粤公网安备 44030502004330号