两个链表的第一个公共结点
问题
输入两个链表,找出它们的第一个公共结点。
class ListNode{
var $val;
var $next = NULL;
function __construct($x){
$this->val = $x;
}
}
分析
- 两链表长度相等,从头至尾循环同步比较,相同结点跳出
- 链表长度不相等,不计数的情况,通过循环达到等长比较效果
上图展示了将较长链表移动至H11位置,即只要达到两链表最终开始移动的指针与各自末尾距离相等即可
- p1,p2同时从头部开始。第一轮p1行至尾,此p2所在位置为它比p1多的起始距离。
- 将p1 重置切换为源p2的副本从头部出发,p2指针继续从第1轮的位置行进
- 当p2指针到末,将其指向源p1副本,源p2副本剩下的长度与p1长度相等(p2c -> end == p1c -> end)。
代码
function FindFirstCommonNode($pHead1, $pHead2)
{
$p1 = $pHead1;
$p2 = $pHead2;
while($p1 != $p2){
$p1 = ($p1==NULL) ? $pHead2 : $p1->next;
$p2 = ($p2==NULL) ? $pHead1 : $p2->next;
}
return $p1;
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: