《剑指Offer》-22.链表中倒数第k个节点

题干

输入一个链表，输出该链表中倒数第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，当第二个指针遍历到链表结尾时，第一个指针所在的节点位置就是中间节点。