题目

编写一个程序，找到两个单链表相交的起始节点。

来源：力扣（LeetCode）

Python解法

双指针＋链表拼接

这道题我原本想的是从两个链表的尾部开始向前寻找，直到找到两链表的节点不同位置，那么该位置的下一个节点就是我们要求的结果。但是这是个单向链表，好像很难实现向前寻找的。

看了题解，发现他们用的是链表拼接的方法来实现的，具体的解题思路如下：
①将两个链表进行拼接，设长-短链表的指针为 PA，短-长链表为 PB （分别代表长链表在前和短链表在前的拼接链表），则当 PA 走到长-短链表交接处时，PB 走在长链表中，且与长链表头距离为长度差；
②当 PA 与 PB 相等时，结束循环，返回 PA 即为最终结果；
③如果长链表与短链表长度相等，如果两个链表有相交节点，那么在指针在遍历到链表交接处之前就会得到最终结果（因为此时两链表没有长度差）；如果两个链表没有相交节点，那么在指针遍历到链表交接处时，会得到两个None，即为最终结果。

代码如下：

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
    PA, PB = headA, headB
    while PA!= PB:
        PA = PA.next if PA else headB
        PB = PB.next if PB else headA
    return PA

正常的思路应该是这样：设定两个指针分别指向两个链表的头部，一起向前走直到其中一个到达末端，另一个与末端距离则是两链表的长度差，再通过长链表指针先走的方式消除长度差。