PHP获取链表中倒数第K个节点的方法

本文实例讲述了PHP获取链表中倒数第K个节点的方法。分享给大家供大家参考，具体如下：

问题

输入一个链表，输出该链表中倒数第k个结点。

解决思路

注意这个题目是返回节点，而不是返回值。返回值的话可以用栈来存储。返回节点则不能这样做。

设置两个指针，先让第一个指针移动k-1次。然后两个指针同时移动，当第一个指针到达最后一个节点，第二个指针就在倒数第k个节点。

注意边界：K长度可能超出链表长度，所以当第一个指针的next为空时，返回null

实现代码

<?php
/*class ListNode{
 var $val;
 var $next = NULL;
 function __construct($x){
  $this->val = $x;
 }
}*/
function FindKthToTail($head, $k)
{
 if($head == NULL || $k ==0)
  return NULL;
 $pre = $head;
 $last = $head;
 for($i=1; $i<$k; $i++){
  if($last->next == NULL)
   return NULL;
  else
   $last = $last->next;
 }
 while($last->next != NULL){
  $pre = $pre->next;
  $last = $last->next;
 }
 return $pre;
}

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

您可能感兴趣的文章:

  • PHP实现找出链表中环的入口节点
  • PHP实现双链表删除与插入节点的方法示例
  • php实现单链表的实例代码
  • PHP 双链表(SplDoublyLinkedList)简介和使用实例
  • PHP小教程之实现双向链表
  • php链表用法实例分析
  • PHP中模拟链表和链表的基本操作示例
  • PHP实现的基于单向链表解决约瑟夫环问题示例
  • PHP实现单链表翻转操作示例
  • php 数据结构之链表队列
  • PHP基于双向链表与排序操作实现的会员排名功能示例
赞 (0)

相关推荐

  • PHP实现的基于单向链表解决约瑟夫环问题示例

    本文实例讲述了PHP实现的基于单向链表解决约瑟夫环问题.分享给大家供大家参考,具体如下: 约瑟夫环问题:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从.首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人.接着,再越

  • php 数据结构之链表队列

    php 链表队列 实例代码: class Queue{ private $last; private $first; private $oldfirst; private static $n=0; public function __construct(){ $this->last = null; $this->first = null; $this->oldfirst = null; } public function push($item){ $this->oldfirst =

  • php链表用法实例分析

    本文实例讲述了php链表用法.分享给大家供大家参考.具体如下: 这里简单介绍了php链表的基本用法,包括链表节点的创建.遍历.更新等操作. <?php /** * @author MzXy * @copyright 2011 * @param PHP链表 */ /** * *节点类 */ class Node { private $Data;//节点数据 private $Next;//下一节点 public function setData($value){ $this->Data=$val

  • PHP 双链表(SplDoublyLinkedList)简介和使用实例

    PHP 双链表(SplDoublyLinkedList)简介和使用实例

    双链表是一种重要的线性存储结构,对于双链表中的每个节点,不仅仅存储自己的信息,还要保存前驱和后继节点的地址. PHP SPL中的SplDoublyLinkedList类提供了对双链表的操作. SplDoublyLinkedList类摘要如下: SplDoublyLinkedList implements Iterator , ArrayAccess , Countable { public __construct ( void ) public void add ( mixed $index ,

  • PHP小教程之实现双向链表

    看了很久数据结构但是没有怎么用过,在网上看到了关于PHP的数据结构,学习了一下,与大家一起分享一下.上一次分享了<PHP小教程之实现链表>,这次来补充说一下双向链表. 复制代码 代码如下: <?php        class Hero        {            public $pre=null;            public $no;            public $name;            public $next=null;           

  • PHP基于双向链表与排序操作实现的会员排名功能示例

    本文实例讲述了PHP基于双向链表与排序操作实现的会员排名功能.分享给大家供大家参考,具体如下: 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.如果不清楚概念的请自行百度. <?php /** * 双向链表实现用户排行榜 * * 仅用于体现思想逻辑,不具备实际参考价值 * @author 疯狂老司机 * @date 2016-07-07 */ class Rank{ /*

  • PHP实现单链表翻转操作示例

    本文实例讲述了PHP实现单链表翻转操作.分享给大家供大家参考,具体如下: 当一个序列中只含有指向它的后继结点的链接时,就称该链表为单链表. 这里给出了一个单链表的定义及翻转操作方法: <?php /** * @file reverseLink.php * @author showersun * @date 2016/03/01 10:33:25 **/ class Node{ private $value; private $next; public function __construct($

  • php实现单链表的实例代码

    复制代码 代码如下: <?php //链表节点 class node {     public $id; //节点id     public $name; //节点名称     public $next; //下一节点 public function __construct($id, $name) {         $this->id = $id;         $this->name = $name;         $this->next = null;     } } /

  • PHP实现双链表删除与插入节点的方法示例

    本文实例讲述了PHP实现双链表删除与插入节点的方法.分享给大家供大家参考,具体如下: 概述: 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 实现代码: <?php class node{ public $prev; public $next; public $data; public function __construct($data,$

  • PHP实现找出链表中环的入口节点

    本文实例讲述了PHP实现找出链表中环的入口节点.分享给大家供大家参考,具体如下: 问题 一个链表中包含环,请找出该链表的环的入口结点. 解决思路 第一步,找环中相汇点.分别用p1,p2指向链表头部,p1每次走一步,p2每次走二步,直到p1==p2找到在环中的相汇点. 第二步,找环的入口.接上步,当p1==p2时,p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数,再让p2指向链表头部,p1位置不变,p1,p

  • PHP中模拟链表和链表的基本操作示例

    模拟链表: <?php /** * PHP实现链表的基本操作 */ class linkList { /** * 姓名 * @var string */ public $name = ''; /** * 编号 * @var int */ public $id = 0; /* * 引用下一个对象 */ public $next = null; /** * 构造函数初始化数据 * @param int $id * @param string $name */ public function __co

随机推荐