给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点.如果两个链表不存在相交节点,返回 null
题目数据 保证 整个链式结构中不存在环
注意,函数返回结果后,链表必须保持其原始结构

思路:
链表必须保持其原始结构,所以不存在靠修改val达成查看是否遍历过节点的方法
解法是将两个链表的长度配平,遍历其中一个链表,遍历完成后继续遍历另一个,总共最大需要遍历的长度是两个链表的长度总和,遍历直到出现相同的节点

代码:
class ListNode
{
    public $val = 0;
    /**
     * @var ListNode|null
     */
    public $next = null;

    function __construct($val = 0, $next = null)
    {
        $this->val  = $val;
        $this->next = $next;
    }
}

/**
 * @param ListNode $headA
 * @param ListNode $headB
 *
 * @return ListNode
 */
function getIntersectionNode($headA, $headB)
{
    $pA = $headA;
    $pB = $headB;

    while($pA !== $pB) {
        //遍历A链表,遍历完成了继续遍历B链表,相当于把A链表接到B链表前面,B链表接到A链表后面
        //让两个链表的长度相同,遍历直到两个链表中出现相同的节点
        $pA = $pA == null ? $headB : $pA->next;
        $pB = $pB == null ? $headA : $pB->next;
    }

    return $pA;
}