[PHP] 算法-复制复杂链表的PHP实现
2023-02-18 15:41:45 时间
复杂链表的复制: 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 } } }
相关文章
- HTTP 状态代码表示什么意思?
- 什么是web框架?
- HTTP真的很简单
- 十分钟搞懂什么是CGI
- HTTP状态码大全(转自wiki)
- 什么是真正的程序员?
- 小printf的故事(未完待续)
- [编辑器]走上atom之路1
- MassTransit 知多少 | 基于StateMachine实现Saga编排式分布式事务
- MassTransit 知多少 | 基于MassTransit Courier实现Saga 编排式分布式事务
- MassTransit 知多少 | .NET 分布式应用框架
- Dapr 知多少 | 分布式应用运行时
- Istio 知多少 | 下一代微服务的守护者
- eShopOnContainers 知多少[12]:Envoy gateways
- 诊断日志知多少 | DiagnosticSource 在.NET上的应用
- Orleans 知多少 | Orleans 中文文档上线
- .NET Core + K8S + Apollo 玩转配置中心
- .NET Core + K8S + Loki 玩转日志聚合
- 五分钟快速搭建Serverless免费邮件服务
- eShopOnContainers 知多少[11]:服务间通信之gRPC