[PHP] 算法-请找出带环链表的环的入口结点的PHP实现

<div class="cnblogs_code">

1.找链表倒数第k个结点,输入一个链表，输出该链表中倒数第k个结点。第一个指针走(k-1)步，到达第k个节点,<span style="color: #000000">两个指针同时往后移动，当第一个结点到达末尾的时候，第二个结点所在位置就是倒数第k个节点了

2.原理有点像上面的，定义两个指针，一个是快指针每次走两步，一个是慢指针每次走一步，当两个相遇的时候，假设环的长度为n个结点，慢指针走x步，快指针走2x步，2x=x+kn ;x=<span style="color: #000000">kn; k暂时假定为1圈 ，也就是慢指针slow走了一个环的距离
3.<span style="color: #000000">快指针回到头结点，慢指针原位置不动，两个每次都是走一步，当两个再次相遇的时候，就是在环入口；想象把环捋直，和倒数第k个结点很像了
slow fast

<span style="color: #0000ff">while fast!=<span style="color: #0000ff">null && fast-><span style="color: #008080">next!=<span style="color: #0000ff">null<span style="color: #000000">

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

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

<span style="color: #0000ff">if slow==<span style="color: #000000">fast

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

<span style="color: #0000ff">while slow!=<span style="color: #000000">fast

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

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

<span style="color: #0000ff">if slow==<span style="color: #000000">fast

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

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

<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">$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("444"<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">$node4-><span style="color: #008080">next=<span style="color: #800080">$node2;<span style="color: #008000">//<span style="color: #008000">尾结点指向第二个结点

<span style="color: #0000ff">function EntryNodeOfLoop(<span style="color: #800080">$pHead<span style="color: #000000">){
<span style="color: #800080">$slow=<span style="color: #800080">$pHead<span style="color: #000000">;
<span style="color: #800080">$fast=<span style="color: #800080">$pHead<span style="color: #000000">;
<span style="color: #0000ff">while(<span style="color: #800080">$fast!=<span style="color: #0000ff">null && <span style="color: #800080">$fast-><span style="color: #008080">next!=<span style="color: #0000ff">null<span style="color: #000000">){
<span style="color: #800080">$slow=<span style="color: #800080">$slow-><span style="color: #008080">next;<span style="color: #008000">//<span style="color: #008000">慢指针走一步
<span style="color: #800080">$fast=<span style="color: #800080">$fast-><span style="color: #008080">next-><span style="color: #008080">next;<span style="color: #008000">//<span style="color: #008000">快指针走两步
//快慢指针环内相遇
<span style="color: #0000ff">if(<span style="color: #800080">$slow==<span style="color: #800080">$fast<span style="color: #000000">){
<span style="color: #008000">//<span style="color: #008000">快指针回到头结点
<span style="color: #800080">$fast=<span style="color: #800080">$pHead<span style="color: #000000">;
<span style="color: #008000">//<span style="color: #008000">同一速度再同时走
<span style="color: #0000ff">while(<span style="color: #800080">$slow!=<span style="color: #800080">$fast<span style="color: #000000">){
<span style="color: #800080">$slow=<span style="color: #800080">$slow-><span style="color: #008080">next<span style="color: #000000">;
<span style="color: #800080">$fast=<span style="color: #800080">$fast-><span style="color: #008080">next<span style="color: #000000">;
}
<span style="color: #008000">//<span style="color: #008000">两个相遇的点一定是环的入口
<span style="color: #0000ff">if(<span style="color: #800080">$slow==<span style="color: #800080">$fast<span style="color: #000000">){
<span style="color: #0000ff">return <span style="color: #800080">$fast<span style="color: #000000">;
}
}
}
}
<span style="color: #008080">var_dump(<span style="color: #800080">$linkList<span style="color: #000000">);
<span style="color: #800080">$result=EntryNodeOfLoop(<span style="color: #800080">$linkList<span style="color: #000000">);
<span style="color: #008080">var_dump(<span style="color: #800080">$result);

<div class="cnblogs_code">

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

（编辑：安卓应用网）

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