leetcode-mid-Linked list-160 Intersection of Two Linked Lists-NO

mycode 用了反转链表，所以不符合题意

参考：

思路：

1 先让长的链表先走，然后相同长度下看是否相遇

class Solution(object):

    def getIntersectionNode(self, headA, headB):

        """

        :type head1, head1: ListNode

        :rtype: ListNode

        """

        if not headA or not headB:

            return None

        def cal(head):

            count = 0

            while head:

                count += 1

                head = head.next

            return count

        countA = cal(headA)

        countB = cal(headB)

        plus = countA - countB

        if plus > 0:

            while plus:

                headA = headA.next

                plus -= 1

            left = countB

        else:

            plus = abs(plus)

            while plus:

                headB = headB.next

                plus -= 1

            left = countA

        while left: #这里无论是headA还是headB都可以啦，因为两个人步伐已经一致啦

            if headA == headB:

                return headA

            headA = headA.next

            headB = headB.next

            left -= 1

        return None

2 让短的链表走到头后，再从长链表的头走起，这样当长链表走完后，短链表刚好在长链表上走了长度的差值的步数，所以长链表再从短链表头开始走的时候，相当于两个人起跑线相同啦

class Solution(object):

    def getIntersectionNode(self, headA, headB):

        if not headA or not headB:

            return None

   

        p,q = headA , headB   

        while p != q:   # 当p不等于q时执行下面程序

            p = headB if p is None else p1.next   # 如果p不是none，就取下一个值，是NONE就让p = headB

            q = headA if q is None else q.next    # 如果q不是none，就取下一个值，是NONE就让q = headA

            

        return p1   # p ，q相等有两种情况，一种是相交了，输出相交点，一种是不相交，输出了NONE

巴特西

leetcode-mid-Linked list-160 Intersection of Two Linked Lists-NO

最新文章

热门文章