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

<div class="cnblogs_code">

1.2.3.1.<span style="color: #000000">

linklist=<span style="color: #000000">head

<span style="color: #0000ff">while linklist!=<span style="color: #0000ff">null<span style="color: #000000">

node=<span style="color: #0000ff">new<span style="color: #000000"> Node()

node-><span style="color: #008080">next=linklist-><span style="color: #008080">next<span style="color: #000000">

linklist-><span style="color: #008080">next=<span style="color: #000000">node

linklist=node-><span style="color: #008080">next

2.<span style="color: #000000">

linklist=<span style="color: #000000">head

<span style="color: #0000ff">while listlink!=<span style="color: #0000ff">null<span style="color: #000000">

node=listlink-><span style="color: #008080">next<span style="color: #000000">

listlink-><span style="color: #008080">next->random=linklist->random!=<span style="color: #0000ff">null  ? listlink->random-><span style="color: #008080">next : <span style="color: #0000ff">null<span style="color: #000000">

listlink=node-><span style="color: #008080">next

3.<span style="color: #000000">

tmp=linklist-><span style="color: #008080">next<span style="color: #000000">

linklist-><span style="color: #008080">next=tmp-><span style="color: #008080">next<span style="color: #000000">

linklist=tmp

<div class="cnblogs_code">

data=
=->==<span style="color: #800080">$node1=<span style="color: #0000ff">new Node("111"<span style="color: #000000">);

<span style="color: #800080">$temp-><span style="color: #008080">next=<span style="color: #800080">$node1<span style="color: #000000">;

<span style="color: #800080">$temp=<span style="color: #800080">$node1<span style="color: #000000">;

<span style="color: #800080">$node2=<span style="color: #0000ff">new Node("222"<span style="color: #000000">);

<span style="color: #800080">$temp-><span style="color: #008080">next=<span style="color: #800080">$node2<span style="color: #000000">;

<span style="color: #800080">$temp=<span style="color: #800080">$node2<span style="color: #000000">;
<span style="color: #800080">$node3=<span style="color: #0000ff">new Node("333"<span style="color: #000000">);

<span style="color: #800080">$node3->random=<span style="color: #800080">$node2; <span style="color: #008000">//<span style="color: #008000">node3又指向了node2

<span style="color: #800080">$temp-><span style="color: #008080">next=<span style="color: #800080">$node3<span style="color: #000000">;

<span style="color: #800080">$temp=<span style="color: #800080">$node3<span style="color: #000000">;
<span style="color: #008080">var_dump(<span style="color: #800080">$linkList<span style="color: #000000">);

<span style="color: #800080">$cloneList=MyClone(<span style="color: #800080">$linkList<span style="color: #000000">);

<span style="color: #008080">var_dump(<span style="color: #800080">$cloneList<span style="color: #000000">);
<span style="color: #008000">//<span style="color: #008000">复制复杂链表

<span style="color: #0000ff">function MyClone(<span style="color: #800080">$linkList<span style="color: #000000">){

<span style="color: #800080">$linkList=<span style="color: #800080">$linkList-><span style="color: #008080">next<span style="color: #000000">;

<span style="color: #008000">//<span style="color: #008000">第一步

<span style="color: #800080">$temp=<span style="color: #800080">$linkList<span style="color: #000000">;

<span style="color: #0000ff">while(<span style="color: #800080">$temp!=<span style="color: #0000ff">null<span style="color: #000000">){

<span style="color: #800080">$node=<span style="color: #0000ff">new Node(<span style="color: #800080">$temp->data.'clone'<span style="color: #000000">);

<span style="color: #800080">$node-><span style="color: #008080">next=<span style="color: #800080">$temp-><span style="color: #008080">next;<span style="color: #008000">//<span style="color: #008000">新结点的next指向当前结点的next

<span style="color: #800080">$temp-><span style="color: #008080">next=<span style="color: #800080">$node;<span style="color: #008000">//<span style="color: #008000">当前结点的next指向新结点

<span style="color: #800080">$temp=<span style="color: #800080">$node-><span style="color: #008080">next;<span style="color: #008000">//<span style="color: #008000">跳两级 跳过新复制的这个结点

<span style="color: #000000">        }

<span style="color: #008000">//<span style="color: #008000">第二步

<span style="color: #800080">$temp=<span style="color: #800080">$linkList<span style="color: #000000">;

<span style="color: #0000ff">while(<span style="color: #800080">$temp!=<span style="color: #0000ff">null<span style="color: #000000">){

<span style="color: #800080">$node=<span style="color: #800080">$temp-><span style="color: #008080">next<span style="color: #000000">;

<span style="color: #008000">//<span style="color: #008000">当前结点的下一级random指向 当前结点random的下一级

<span style="color: #800080">$temp-><span style="color: #008080">next->random=<span style="color: #800080">$temp->random!=<span style="color: #0000ff">null ? <span style="color: #800080">$temp->random-><span style="color: #008080">next : <span style="color: #0000ff">null<span style="color: #000000">;

<span style="color: #800080">$temp=<span style="color: #800080">$node-><span style="color: #008080">next<span style="color: #000000">;

}

<span style="color: #008000">//<span style="color: #008000">第三步

<span style="color: #800080">$newList=<span style="color: #800080">$linkList-><span style="color: #008080">next;<span style="color: #008000">//<span style="color: #008000">从第二个结点开始要

<span style="color: #800080">$temp=<span style="color: #800080">$newList<span style="color: #000000">;

<span style="color: #0000ff">while(<span style="color: #800080">$temp-><span style="color: #008080">next!=<span style="color: #0000ff">null<span style="color: #000000">){

<span style="color: #800080">$node=<span style="color: #800080">$temp-><span style="color: #008080">next;<span style="color: #008000">//<span style="color: #008000">获取当前结点的next

<span style="color: #800080">$temp-><span style="color: #008080">next=<span style="color: #800080">$node-><span style="color: #008080">next;<span style="color: #008000">//<span style="color: #008000">当前结点的next指向 下一级的next,这样就消掉了下一个

<span style="color: #800080">$temp=<span style="color: #800080">$node;<span style="color: #008000">//<span style="color: #008000">当前结点后移

<span style="color: #000000">        }

<span style="color: #0000ff">return <span style="color: #800080">$newList<span style="color: #000000">;

}

<div class="cnblogs_code">

(Node)
  ["data"]=>
  (0) """random"]=>
  "next"]=>
  (Node)
    ["data"]=>
    (3) "111""random"]=>
    "next"]=>
    (Node)
      ["data"]=>
      (3) "222""random"]=>
      "next"]=>
      (Node)
        ["data"]=>
        (3) "333""random"]=>
        *RECURSION*"next"]=>
        (Node)
  ["data"]=>
  (8) "111clone""random"]=>
  "next"]=>
  (Node)
    ["data"]=>
    (8) "222clone""random"]=>
    "next"]=>
    (Node)
      ["data"]=>
      (8) "333clone""random"]=>
      *RECURSION*"next"]=>
      

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!