【剑指offer】两个链表的第一个公共结点（python）

纪念一下，第一次一遍过！很棒，加油！
思路是双指针，一个遍历链表1，一个遍历链表2，需要注意的是指针复制的地方，链表2的指针是外部的，不需要复制，遍历到尾部就拉倒了，但是链表1的指针是内部的，需要复制，复制的地方在外循环内、内循环外。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        if pHead1 is None or pHead2 is None:
            return None
        while pHead2 is not None:
            p1 = pHead1
            while p1 is not None:
                if p1.val == pHead2.val:
                    return p1
                else:
                    p1 = p1.next
            pHead2 = pHead2.next
        return None

好家伙，大神的代码更牛逼。

直接用 p1 is not p2 判断两个结点是否相等
python 三元运算符，“为真时的结果 if 判定条件 else 为假时的结果”
p1 = p1.next if p1 else pHead2
p2 = p2.next if p2 else pHead1
复杂写法就是：
if p1:
p1 = p1.next
else:
p1 = pHead2
if p2:
p2 = p2.next
else:
p2 = pHead1
用两个指针扫描两个链表，最终两个指针到达 null 或者到达公共结点。短链表指针先走完，然后指向长链表，指向长链表指针后走完，指向短链表。所以，第二次走过，一定会在交点相遇。
长度相同有公共结点，第一次就遍历到；没有公共结点，走到尾部NULL相遇，返回NULL，长度不同有公共结点，第一遍差值就出来了，第二遍一起到公共结点；没有公共，一起到结尾NULL。
这里先假设链表A头结点与结点8的长度与链表B头结点与结点8的长度相等，那么就可以用双指针。

初始化：指针ta指向链表A头结点，指针tb指向链表B头结点
如果ta == tb，说明找到了第一个公共的头结点，直接返回即可。
否则，ta != tb，则++ta，++tb
图片说明
所以现在的问题就变成，如何让本来长度不相等的变为相等的？
假设链表A长度为a，链表B的长度为b，此时a != b
但是，a+b == b+a
因此，可以让a+b作为链表A的新长度，b+a作为链表B的新长度。
如图：

这样，长度就一致了，可以用上述的双指针解法了。
时间复杂度：O(m+n), m，n分别为链表A，B的长度，最坏情况下，公共结点为最后一个，需要遍历m+n个结点

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        p1, p2 = pHead1, pHead2
        while p1 is not p2:
            p1 = p1.next if p1 else pHead2
            p2 = p2.next if p2 else pHead1
        return p1

题解 | #两个链表的第一个公共结点#

【剑指offer】两个链表的第一个公共结点（python）