两个链表的第一个公共结点

剑指Offer - PHP /

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

分析

如图两条链表中，第一个公共节点是8（1只是第一个值相同的节点而已）。
Ce5gLkmldL.png!large

设两条链表为公共节点的长度是C，链表A的长度为LA + C，链表B的长度为LB + C。
链表A走完LA + C长度的节点后，再走LB长度。链表B走完LB + C长度的节点后，再走LA长度的节点。此时，两链表走过的长度都为LA + LB + C，即最后在公共节点相遇。

代码

<?php
/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/ 
function FindFirstCommonNode($pHead1, $pHead2)
{
    $node1 = $pHead1;   // 指针 $node1 指向头结点
    $node2 = $pHead2;   // 指针 $node2 指向头结点

    // 当两个节点还未相遇，则往下走。走到最后一个节点时，则往另一条链表头节点开始。
    while ($node1 != $node2) {
        $node1 = $node1 != NULL ? $node1->next : $pHead2;
        $node2 = $node2 != NULL ? $node2->next : $pHead1;
    }
    return $node1;
}