Simple Python solution (Assume from intersection to tail is same)


  • 4
    A

    I assume from intersection node to the end is same, which mean after they intersecting, they won't divide.
    So I only need to check after they have the same length and return the first node is same.

    class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        sizeA = 0
        sizeB = 0
        p1 = headA
        p2 = headB
        while p1:
            p1 = p1.next
            sizeA += 1
        while p2:
            p2 = p2.next
            sizeB += 1
        
        while sizeA != sizeB:
            if sizeA > sizeB:
                headA = headA.next
                sizeA -= 1
            elif sizeB > sizeA:
                headB = headB.next
                sizeB -= 1
        
        while headA and headB:
            if headA==headB:
                return headA
            headA = headA.next
            headB = headB.next
        
        return None

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.