相交链表

image.png

• 双指针思想，两个指针同时移动，在经过a+b+c的长度后会在交点相遇，应该是最优解法。
• 直接判断两个node是否相等而非判断其val相等即可
• 或许也可以构建两个链表对应的倒序链表，然后从头开始比较即可，时间复杂度稍微高点。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA is None or headB is None:
            return None
        pA = headA
        pB = headB
        while pA != pB and (pA or pB):
            if pA is None:
                pA=headB
            else:
                pA=pA.next
            if pB is None:
                pB=headA
            else:
                pB=pB.next
        if pA is None:
            return None
        else:
            return pA
         ```