剑指offer--链表中环的入口节点（PHP）

题目：一个链表中包含环，请找出该链表的环的入口结点。

刚拿到这个题目时，完全是懵的状态。本来这段时间都在做关于链表的题目，但是，真的每个题目都不一样，完全是另外的跟之前的题目大相径庭的。但是，在解题过程中，前面所学到的东西还是有用的。比如：&& 等。

思路：利用链表中有环，如果遍历链表的时候一个指针跑得快，另一个指针跑得慢，总会出现快的追上慢的。当追上的时候，慢的指针所走（从首节点开始）的路径长度一定是出现环的节点的数目。而快的指针所走的路径长度比慢的指针的路径长度一个环的长度。

求入口节点：当第一次慢快指针相遇时，让第三个指针从头开始指向头结点。每次向前走一步。当第三个指针和第第一个指针相遇时的节点即为，环的入口节点。、

代码为：

function EntryNodeOfLoop($pHead)
{
    // write code here
    if($pHead == null)return $pHead;
    $p1 = $pHead;
    $p2 = $pHead;
    while($p2 && $p1){
        $p1 = $p1->next;
        $p2 = $p2->next->next;
        if($p1 == $p2){
            $p3 = $pHead;
            while($p1 && $p3){
                if($p1 == $p3){
                    return $p3;
                }               //这里特别说明当出现，该链表即为环链表时（第一个节点即为入口节点）
                                  当第一次相遇的地方就是第一节点的地方。
              $p1 = $p1->next;
                $p3 = $p3->next;
                if($p1 == $p3){
                    return $p3;
                }
            }
        }
    }
}

2：该题还有其他解法，到时候再更新。

帮助理解：点击打开链接

更多相关文章

随机推荐