链表中倒数第k个节点

剑指Offer - PHP /

题目描述

输入一个链表，输出该链表中倒数第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;  // 返回链表
}