[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
    }
  }
}