【php】链表的翻转&判断链表是否有环

• Z时代
• 2024-01-10
• 分类：技术分享

<?php
require 'LinkedList.php';
$linkedList = new LinkedList();
for ($i = 1;$i <= 20;$i++){
$linkedList->addFirst($i);
}
echo $linkedList->toString();
/**
* 20->19->18->17->16->15->14->13->12->11->10->9->8->7->6->5->4->3->2->1->null
*/
echo "n";
function reverse($head){
$pre = $head;
$cur = $head->next;
while ($cur){
$next = $cur->next;
$cur->next = $pre;
$pre = $cur;
$cur = $next;
}
$head->next = null;
return $pre;
}
$linkedList->setHead(reverse($linkedList->getHead()));
echo $linkedList->toString();
/**
* 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->null
*/
echo "n";

<?php
class Node
{
public $e;//节点元素
public $next; //下个节点信息
/**
* 构造函数 设置节点信息
* Node constructor.
* @param $e
* @param $next
*/
public function __construct($e, $next=null) {
$this->e = $e;
$this->next = $next;
}
}
function isLoop($head){
$fast = $head;
$slow = $head;
$i = 1;
while ($fast !== null && $slow !== null){
if($fast === $slow){
return true;
}
$fast = $fast->next->next ?? null; //每次跳两步
$slow = $slow->next ?? null;  //每次跳一步
if($i)
$i++;
}
return false;
}
$node1 = new Node(1);
$node2 = new Node(2);
$node3 = new Node(3);
$node4 = new Node(4);
$node5 = new Node(5);
$node6 = new Node(6);
$node7 = new Node(7);
$node8 = new Node(8);
$node9 = new Node(9);
$node1->next = $node2;
$node2->next = $node3;
$node3->next = $node4;
$node4->next = $node5;
$node5->next = $node6;
$node6->next = $node7;
$node7->next = $node8;
$node8->next = $node9;
$node9->next = $node5;
var_dump(isLoop($node1));

​通过学习 链表的翻转 和 判断链表是否有环 这两个简单的例子加深对链表这种数据结构的理解。

1.链表翻转

1.1 链表翻转原理图

1.2 链表翻转代码

<?php
require 'LinkedList.php';
$linkedList = new LinkedList();
for ($i = 1;$i <= 20;$i++){
$linkedList->addFirst($i);
}
echo $linkedList->toString();
/**
* 20->19->18->17->16->15->14->13->12->11->10->9->8->7->6->5->4->3->2->1->null
*/
echo "n";
function reverse($head){
$pre = $head;
$cur = $head->next;
while ($cur){
$next = $cur->next;
$cur->next = $pre;
$pre = $cur;
$cur = $next;
}
$head->next = null;
return $pre;
}
$linkedList->setHead(reverse($linkedList->getHead()));
echo $linkedList->toString();
/**
* 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->null
*/
echo "n";

演示输出如下图：

2.判断链表是否有环

2.1 链表环示意图

2.2 问题分析

在遍历链表的时候可以维护 快 和 慢 两个指针赋值，可以将这两个快慢插设为 1，当遍历到环上面的时候，由于维护的两个指针的快慢相差 1,最后肯定会有相遇的时候，若出现相遇的情况则表示有环，若快指针最后指向 null 表示没有环。

2.3 原理图

2.4 示例代码

<?php
class Node
{
public $e;//节点元素
public $next; //下个节点信息
/**
* 构造函数 设置节点信息
* Node constructor.
* @param $e
* @param $next
*/
public function __construct($e, $next=null) {
$this->e = $e;
$this->next = $next;
}
}
function isLoop($head){
$fast = $head;
$slow = $head;
$i = 1;
while ($fast !== null && $slow !== null){
if($fast === $slow){
return true;
}
$fast = $fast->next->next ?? null; //每次跳两步
$slow = $slow->next ?? null;  //每次跳一步
if($i)
$i++;
}
return false;
}
$node1 = new Node(1);
$node2 = new Node(2);
$node3 = new Node(3);
$node4 = new Node(4);
$node5 = new Node(5);
$node6 = new Node(6);
$node7 = new Node(7);
$node8 = new Node(8);
$node9 = new Node(9);
$node1->next = $node2;
$node2->next = $node3;
$node3->next = $node4;
$node4->next = $node5;
$node5->next = $node6;
$node6->next = $node7;
$node7->next = $node8;
$node8->next = $node9;
$node9->next = $node5;
var_dump(isLoop($node1));

演示输出如下图：

代码仓库 ：https://gitee.com/love-for-po...

扫码关注爱因诗贤

以上是 【php】链表的翻转&判断链表是否有环 的全部内容， 来源链接： utcz.com/a/107039.html