Simple and clean Python solution with comments


  • 0
    P

    class Solution(object):

    def get_length_LL(self, node):
        counter = 0
        while node != None:
            counter += 1
            node = node.next
        
        return counter
    
    
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
    
        length_A = self.get_length_LL(headA)
        length_B = self.get_length_LL(headB)
        
        if length_A == 0 or length_B == 0:
            return None
        
        diff = abs(length_A - length_B)
    
        pointer_A = headA
        pointer_B = headB
    
        # Find which one is longer 
        if length_A > length_B:
            # Advance pointer of A by the diff
            for x in range(diff):
                pointer_A = pointer_A.next
        else:
            # Advance pointer of B by the diff
            for x in range(diff):
                pointer_B = pointer_B.next
            
    
        # Now both of them have same number of iterations left
        while pointer_A !=None and pointer_B !=None:
            if pointer_A == pointer_B:
                return pointer_A
            else:
                # Update the two pointers
                pointer_A = pointer_A.next
                pointer_B = pointer_B.next
    
                # Check if one of them is empty before the other 
                if (pointer_A == None and pointer_B != None) or (pointer_B == None and pointer_A != None):
                    return None
        
    
        # If we end up here, it means that there was no intersection       
        return None

Log in to reply
 

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