通过学习 链表的翻转 和 判断链表是否有环 这两个简略的例子加深对链表这种数据结构的了解。
1.链表翻转
1.1 链表翻转原理图
1.2 链表翻转代码
<?phprequire '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 示例代码
<?phpclass 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...
扫码关注爱因诗贤