8-1 相交链表

用户头像
burner
关注
发布于: 2020 年 07 月 29 日

时间复杂度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



发布于: 2020 年 07 月 29 日 阅读数: 6
用户头像

burner

关注

还未添加个人签名 2018.08.07 加入

还未添加个人简介

评论

发布
暂无评论
8-1 相交链表