题解 | #两个链表的第一个公共结点#
两个链表的第一个公共结点
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
<?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ function FindFirstCommonNode($pHead1, $pHead2) { if($pHead1 == null || $pHead2 == null){ return null; } $len1 = 0; $p1 = $pHead1; $p11 = $pHead1; $p2 = $pHead2; $p21 = $pHead2; while($p1 != null || $p2 != null){ if($p1 == null){ $p21 = $p21->next; }else{ $p1 = $p1->next; } if($p2 == null){ $p11 = $p11->next; }else{ $p2 = $p2->next; } } while($p11 != null && $p21 != null){ if($p11 == $p21){ return $p11; } $p11 = $p11->next; $p21 = $p21->next; } return null; }
两个链表的第一个公共节点后一定是一样的,所以可以长的链表先走|len1-len2|步,然后两个链表指针一起移动,判断指针相同就是第一个公共节点。
注意:可以只用一个while来让长的链表多走,短链表指针==null之后,长链表头部指针向后移动1