时间复杂度O（N+M）；空间复杂度O（1）



class Solution(object):



    # 根据题目意思



    # 如果两个链表相交，那么相交点之后的长度是相同的



    # 换个方式消除长度差： 拼接两链表。



    # 设长-短链表为 C，短-长链表为 D （分别代表长链表在前和短链表在前的拼接链表），



    # 则当 C 走到长短链表交接处时，D 走在长链表中，且与长链表头距离为 长度差;



    # 拼接之后，当消除掉长度差，那么如果相交，肯定两个节点ha和hb会想等；



    # 如果不相交，两个拼接后的长度也一样，最终都会是null，然后退出



    def getIntersectionNode(self, headA, headB):



        """



        :type head1, head1: ListNode



        :rtype: ListNode



        """



        if not headA:



            return None



        if not headB:



            return None



        ha, hb = headA, headB



        while ha != hb:



            ha = ha.next if ha else headB



            hb = hb.next if hb else headA



        return ha