PHP implémente du code pour copier des listes chaînées complexes

Le contenu de cet article concerne le code pour copier des listes chaînées complexes en PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Copie de la liste chaînée complexe :
1. Copiez un nœud derrière chaque nœud dans l'ancienne liste chaînée, sautez les générations
2. Pointez sur la partie aléatoire de l'ancienne liste chaînée, Copier vers le nœud nouvellement ajouté
3. Divisez le nouveau nœud de l'ancienne liste chaînée en une nouvelle liste chaînée

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

Recommandations associées :

Partage de code de copie Java pour implémenter une liste chaînée complexe

Exemple de code PHP pour implémenter une liste chaînée unique

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!