[PHP] 算法-复制复杂链表的PHP实现
2023-02-18 15:47:19 时间
复杂链表的复制: 1.在旧链表中每个结点的后面复制出一个结点,隔代 2.把旧链表的随机指向部分,复制到新添加的结点上 3.把新结点从旧链表中拆分出来成新链表 1. linklist=head while linklist!=null node=new Node() node->next=linklist->next linklist->next=node linklist=node->next 2. linklist=head while listlink!=null node=listlink->next listlink->next->random=linklist->random!=null ? listlink->random->next : null listlink=node->next 3. tmp=linklist->next linklist->next=tmp->next linklist=tmp
<?php class Node{ public $data; public $random; public $next; public function __construct($data=""){ $this->data=$data; } } //构造一个复杂链表 $linkList=new Node(); $linkList->next=null; $temp=$linkList; $node1=new Node("111"); $temp->next=$node1; $temp=$node1; $node2=new Node("222"); $temp->next=$node2; $temp=$node2; $node3=new Node("333"); $node3->random=$node2; //node3又指向了node2 $temp->next=$node3; $temp=$node3; var_dump($linkList); $cloneList=MyClone($linkList); var_dump($cloneList); //复制复杂链表 function MyClone($linkList){ $linkList=$linkList->next; //第一步 $temp=$linkList; while($temp!=null){ $node=new Node($temp->data.'clone'); $node->next=$temp->next;//新结点的next指向当前结点的next $temp->next=$node;//当前结点的next指向新结点 $temp=$node->next;//跳两级 跳过新复制的这个结点 } //第二步 $temp=$linkList; while($temp!=null){ $node=$temp->next; //当前结点的下一级random指向 当前结点random的下一级 $temp->next->random=$temp->random!=null ? $temp->random->next : null; $temp=$node->next; } //第三步 $newList=$linkList->next;//从第二个结点开始要 $temp=$newList; while($temp->next!=null){ $node=$temp->next;//获取当前结点的next $temp->next=$node->next;//当前结点的next指向 下一级的next , 这样就消掉了下一个 $temp=$node;//当前结点后移 } return $newList; }
object(Node)#1 (3) { ["data"]=> string(0) "" ["random"]=> NULL ["next"]=> object(Node)#2 (3) { ["data"]=> string(3) "111" ["random"]=> NULL ["next"]=> object(Node)#3 (3) { ["data"]=> string(3) "222" ["random"]=> NULL ["next"]=> object(Node)#4 (3) { ["data"]=> string(3) "333" ["random"]=> *RECURSION* ["next"]=> NULL } } } } object(Node)#5 (3) { ["data"]=> string(8) "111clone" ["random"]=> NULL ["next"]=> object(Node)#6 (3) { ["data"]=> string(8) "222clone" ["random"]=> NULL ["next"]=> object(Node)#7 (3) { ["data"]=> string(8) "333clone" ["random"]=> *RECURSION* ["next"]=> NULL } } }
相关文章
- [PHP] PHP PDO与mysql的连接单例防止超时情况处理
- [PHP] 使用Socket提供Http服务
- [PHP] 实现路由映射到指定控制器
- [PHP] 命令行执行整合pathinfo模拟定时任务
- [PHP] 自定义错误处理
- [Php] windows下使用composer出现SHA384 is not supported by your openssl extension
- [PHP] url的pathinfo模式加载不同控制器的实现
- [PHP] 自动加载的实现
- [PHP] 新版本PHP7.4与新版本MySQL8认证问题
- [PHP] PHP请求Socket接口测试
- [PHP] error_reporting(0)可以屏蔽Fatal error错误
- [PHP] 读取大文件并显示
- [PHP] PDO对象与mysql的连接超时
- [PHP] time_wait与长连接短连接
- [PHP] Ubuntu快速安装起PHP7.4
- [PHP] CentOS下搭建下PHP的运行环境
- [日常] 修复了grub引导问题
- [MySQL] docker下安装使用mysql配置主从复制
- [日常] lscpu查看cpu的详细信息
- [日常] 高并发抢购方案的思考