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

问题

输入两个链表,找出它们的第一个公共结点。

class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}

分析

  • 两链表长度相等,从头至尾循环同步比较,相同结点跳出
  • 链表长度不相等,不计数的情况,通过循环达到等长比较效果

两个链表的第一个公共结点
上图展示了将较长链表移动至H11位置,即只要达到两链表最终开始移动的指针与各自末尾距离相等即可

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

  1. p1,p2同时从头部开始。第一轮p1行至尾,此p2所在位置为它比p1多的起始距离。
  2. 将p1 重置切换为源p2的副本从头部出发,p2指针继续从第1轮的位置行进
  3. 当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 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!
开发者 @ 社科大
文章
102
粉丝
12
喜欢
82
收藏
38
排名:102
访问:4.6 万
私信
所有博文