[PHP] 算法-删除链表中重复的结点的PHP实现

发布时间：2020-05-25 03:11:16 所属栏目：PHP 来源：互联网

导读：删除链表中重复的结点：1.定义两个指针pre和current2.两个指针同时往后移动，current指针如果与后一个结点值相同，就独自往前走直到没有相等的3.pre指针next直接指向current指针的后一个，把相同的都跳过pre=linkListcurrent=linkListwhile current!=nullif c

1.2.3.pre=<span style="color: #000000">linkList

<span style="color: #008080">current=<span style="color: #000000">linkList

<span style="color: #0000ff">while <span style="color: #008080">current!=<span style="color: #0000ff">null

<span style="color: #0000ff">if <span style="color: #008080">current->data==<span style="color: #008080">current-><span style="color: #008080">next-><span style="color: #000000">data

value=<span style="color: #008080">current-><span style="color: #000000">data

<span style="color: #0000ff">while value==<span style="color: #008080">current-><span style="color: #008080">next-><span style="color: #000000">data

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

pre-><span style="color: #008080">next=<span style="color: #008080">current-><span style="color: #008080">next<span style="color: #000000">

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

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

<span style="color: #0000ff">return linkList

data=
=->==<span style="color: #800080">$node1=<span style="color: #0000ff">new Node(2<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(2<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(3<span style="color: #000000">);

<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: #800080">$node4=<span style="color: #0000ff">new Node(3<span style="color: #000000">);

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

<span style="color: #800080">$temp=<span style="color: #800080">$node4<span style="color: #000000">;
<span style="color: #800080">$node5=<span style="color: #0000ff">new Node(4<span style="color: #000000">);

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

<span style="color: #800080">$node5-><span style="color: #008080">next=<span style="color: #0000ff">null<span style="color: #000000">;
<span style="color: #0000ff">function deleteDuplication(<span style="color: #800080">$pHead<span style="color: #000000">){

<span style="color: #800080">$pre=<span style="color: #800080">$pHead-><span style="color: #008080">next;<span style="color: #008000">//<span style="color: #008000">当前都指向第一个结点

<span style="color: #800080">$current=<span style="color: #800080">$pHead-><span style="color: #008080">next;<span style="color: #008000">//<span style="color: #008000">当前结点是第一个结点

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

<span style="color: #008000">//<span style="color: #008000">如果当前结点值和当前结点的下一个结点值相同

<span style="color: #0000ff">if(<span style="color: #800080">$current-><span style="color: #008080">next!=<span style="color: #0000ff">null && <span style="color: #800080">$current->data==<span style="color: #800080">$current-><span style="color: #008080">next-><span style="color: #000000">data){

<span style="color: #008000">//<span style="color: #008000">保存当前结点值

<span style="color: #800080">$val=<span style="color: #800080">$current-><span style="color: #000000">data;

<span style="color: #008000">//<span style="color: #008000">当前结点往后移直到和下一个结点值不相等

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

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

}

<span style="color: #008000">//<span style="color: #008000">前一个指针next直接指向当前结点的next

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

}

<span style="color: #008000">//<span style="color: #008000">两个指针同时后移

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

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

}

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

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

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

<span style="color: #008080">var_dump(<span style="color: #800080">$result);

(Node)
  ["data"]=>
  (0) """next"]=>
  (Node)
    ["data"]=>2"next"]=>
    (Node)
      ["data"]=>2"next"]=>
      (Node)
        ["data"]=>3"next"]=>
        (Node)
          ["data"]=>3"next"]=>
          (Node)
            ["data"]=>4"next"]=>
            (Node)
  ["data"]=>
  (0) """next"]=>
  (Node)
    ["data"]=>2"next"]=>
    (Node)
      ["data"]=>3"next"]=>
      (Node)
        ["data"]=>4"next"]=>

（编辑：安卓应用网）

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