欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[PHP] 数据结构-输出链表倒数第k个结点PHP实现

程序员文章站 2022-06-22 11:12:53
输入一个链表,输出该链表中倒数第k个结点。第一个指针走(k-1)步,到达第k个节点,两个指针同时往后移动,当第一个结点到达末尾的时候,第二个结点所在位置就是倒数第k个节点了 ......

输入一个链表,输出该链表中倒数第k个结点。第一个指针走(k-1)步,到达第k个节点,两个指针同时往后移动,当第一个结点到达末尾的时候,第二个结点所在位置就是倒数第k个节点了

<?php
class node{
        public $data;
        public $next;
}
//创建一个链表
$linklist=new node();
$linklist->next=null;
$temp=$linklist;
for($i=1;$i<=10;$i++){
        $node=new node();
        $node->data="aaa{$i}";
        $node->next=null;
        $temp->next=$node;
        $temp=$node;
}
//输入一个链表,输出该链表中倒数第k个结点。

function find($linklist,$k){
        //速度快的指针
        $fast=$linklist;
        //速度慢的指针
        $slow=$linklist;
        //快指针先移动k-1步
        for($i=0;$i<$k-1;$i++){
                $fast=$fast->next;
        }   
        if($fast->next==null){
                return false;
        }   
        //快慢指针一块移动
        while($fast->next!=null){
                $fast=$fast->next;
                $slow=$slow->next;
        }   
        return $slow;
}


$knode=find($linklist,2);
var_dump($knode);
object(node)#10 (2) {
  ["data"]=>
  string(4) "aaa9"
  ["next"]=>
  object(node)#11 (2) {
    ["data"]=>
    string(5) "aaa10"
    ["next"]=>
    null
  }
}