题干
输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始技术，即链表的尾节点是倒数第1个节点。例如：一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。链表节点定义如下：
class ListNode {
int val;
ListNode next;
}
解题思路
思路一 遍历两遍
先遍历一遍链表，得到链表中节点的个数n，然后再遍历一遍链表，当遍历到第n-k+1个节点时停止，该节点就是倒数第k个节点。
倒数第k个节点 = 节点总数n - k + 1
思路二 遍历一遍
使用两个指针，第一个指针比第二个指针先遍历 ++k-1++ 个节点，然后两个指针一起开始遍历，当第一个指针到达链表尾部时，第二个指针所在的节点就是倒数第k个节点。
代码实现
<?php
class ListNode
{
private $val;
private $next;
public function __set($name, $value)
{
$this->$name = $value;
}
public function __get($name)
{
return $this->$name;
}
}
$node1 = new ListNode();
$node1->val = 1;
$node2 = new ListNode();
$node2->val = 2;
$node1->next = $node2;
$node3 = new ListNode();
$node3->val = 3;
$node2->next = $node3;
$node4 = new ListNode();
$node4->val = 4;
$node3->next = $node4;
$node5 = new ListNode();
$node5->val = 5;
$node4->next = $node5;
function findKthNode(ListNode $head = null, $k)
{
if (empty($head) || $k <= 0) {
return '输入参数错误！';
}
$first = $head;
for ($i = 0; $i < $k - 1; $i++) {
if ($first->next) {
$first = $first->next;
} else {
return "输入参数k的值超过链表长度";
}
}
$second = $head;
while ($first->next) {
$second = $second->next;
$first = $first->next;
}
return $second->val;
}
echo findKthNode($node1, 1);
举一反三
求链表的中间节点，如果链表中的节点总数为奇数，则返回中间节点，如果节点总数为偶数，则返回中间两个节点中的任意一个。
使用两个指针同时从头开始遍历，一个指针的步长是1，一个指针的步长是2，当第二个指针遍历到链表结尾时，第一个指针所在的节点位置就是中间节点。
