共计 1578 个字符,预计需要花费 4 分钟才能阅读完成。
通过学习 链表的翻转
和 判断链表是否有环
这两个简略的例子加深对链表这种数据结构的了解。
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…
扫码关注爱因诗贤
正文完