剑指Offer - PHP两个链表的第一个公共结点
题目描述
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
分析
如图两条链表中，第一个公共节点是8（1只是第一个值相同的节点而已）。
设两条链表为公共节点的长度是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;
}
关于 LearnKu
粤公网安备 44030502004330号