专栏首页陶士涵的菜地[PHP] 算法-复制复杂链表的PHP实现

[PHP] 算法-复制复杂链表的PHP实现

复杂链表的复制:
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
    }
  }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [日常] 算法-单链表的创建

    2.循环中创建结点,把头结点的next赋值给 新结点的next,相当于新结点的next指向了(头结点next所指向的)

    陶士涵
  • [PHP] 数据结构-链表创建-插入-删除-查找的PHP实现

    链表获取元素 1.声明结点p指向链表第一个结点,j初始化1开始 2.j<i,p指向下一结点,因为此时p是指向的p的next,因此不需要等于 3.如果到末尾了,p...

    陶士涵
  • [PHP] 数据结构-循环链表的PHP实现

    1.将单链表中终端结点的指针端由空指针改为指向头结点,单循环链表,循环链表和单链表的主要差异就在于循环的判断条件上 原来是判断p->next是否为空,现在则是p...

    陶士涵
  • leetcode: 206. Reverse Linked List

    JNingWei
  • leetcode:83 删除排序链表中的重复元素

    问题? 如果next没有值的话,会报错的。 因为要相等啊,比较啊,有值才能比较是吧。 那为什么p.next=p.next.next;如果p.next.ne...

    用户7873631
  • 模式匹配KMP算法

    匹配到j=5时失效了,BF算法里我们会使i=1,j=0,再看s的第i位开始能不能匹配,而KMP算法接下来就去比较T[2](next[5]=2)和S[5]

    饶文津
  • c/c++补完计划(七): 哨兵节点

    sean_yang
  • 【玩转腾讯云】python next函数

    python 3.x内置函数next可以从迭代器中检索下一个元素或者数据,可以用于迭代器遍历,使用的时候注意会触发 StopIteration 异常!

    猿说编程[Python和C]
  • 吃透洋葱模型

    作者:掘金@苏里 https://juejin.im/post/6844904025767280648

    zz_jesse
  • 【力扣】_92反转链表II

    瑞新

扫码关注云+社区

领取腾讯云代金券