Simple Python solution using set (runtime beats 80%)


  • 0
    P

    The idea is to maintain a set (or hashmap) containing visited nodes. Those nodes which have already been visited are added to the set and then both heads are pointed to the next nodes in the sequence. If either of the new head (node) is already in the visited set of nodes then that head (node) is the answer. Also, if both heads happen to point to the same node then return either head (node). Here is the code:

        def getIntersectionNode(self, headA, headB):
            visited = set()
    
            while (headA is not headB):
    
                if headA:
                    if headA in visited:
                        return headA
                    else:
                        visited.add(headA)
                        headA = headA.next
    
                if headB:
                    if headB in visited:
                        return headB
                    else:
                        visited.add(headB)
                        headB = headB.next
            
            # If headA and headB are equal
            return headA
    

Log in to reply
 

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