PHP implements code for copying complex linked lists

The content of this article is about the code for copying complex linked lists in PHP. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Copy of complex linked list:
1. Copy a node behind each node in the old linked list, skip generations
2. Copy the random pointing part of the old linked list, Copy to the newly added node
3. Split the new node from the old linked list into a new linked list

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.&#39;clone&#39;);
                $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
    }
  }
}

Related recommendations:

Java Sharing the copy code to implement a complex linked list

php example code to implement a singly linked list

The above is the detailed content of PHP implements code for copying complex linked lists. For more information, please follow other related articles on the PHP Chinese website!