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

码农天地 - 2020-12-09 05:59:42

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

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...

扫码关注爱因诗贤

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。