Python solution with some thoughts analysis


  • 0
    L
       def getIntersectionNode(self, headA, headB):
                if headA==None or headB==None:
                    return None
                cur1=headA
                cur2=headB
                count1=count2=0
                while cur1!=None:
                    count1+=1
                    cur1=cur1.next
                while cur2!=None:
                    count2+=1
                    cur2=cur2.next
                cur1=headA
                cur2=headB
                if count1>count2:
                    i=0
                    while cur1!=None and i<count1-count2:
                        cur1=cur1.next
                        i+=1
                else:
                    i=0
                    while cur2!=None and i<count2-count1:
                        cur2=cur2.next
                        i+=1
                while cur1!=None and cur2!=None and cur1!=cur2:
                    cur1=cur1.next
                    cur2=cur2.next
                return cur1
    
    1. O(n^2)time and O(1) space: it's straight
    2. O(n) time and O(n) space:
      (1) set two boolean hashtable: visitedA and visitedB, default are false
      (2) Traversal linked lists A, and set the visitedA[currentNodeA]=True
      (3) Go through linked lists B, and check if vistedB[currentNodeB]==True, yes:return currentNodeB; no:continue.
    3. O(n) time and O(1) space:
      (1) find the size of each linked list:
      (2) move the longer linked list pointer, say curA, ahead d steps, where d=|sizeA-sizeB|
      (3) move curB and curA one node per step until they meet.

  • 0
    L

    your code looks complicated, here is my simple O(m+n) solution. the main idea is very straightforward:

    def getIntersectionNode(self, headA, headB):
            if headA and headB:
                current_a, current_b = headA, headB
                while True:
                    if current_a == current_b:
                        return current_b
                        
                    current_a = current_a.next
                    current_b = current_b.next
                    
                    if current_a == current_b:
                        return current_b
                        
                    if current_a is None: 
                        current_a = headB
                    if current_b is None: 
                        current_b = headA
    

  • 0
    L
    This post is deleted!

  • 0
    L

    That's a nice thought


  • 0
    P

    @LeoShi your code is not working, when headA is None or headB is None,it still jump into while loop.The code here works:

        def getIntersectionNode(self, headA, headB):
            if headA is None or headB is None:
                return None
            current_a, current_b = headA, headB
            while True:
                if current_a == current_b:
                    return current_b
    
                current_a = current_a.next
                current_b = current_b.next
    
                if current_a == current_b:
                    return current_b
    
                if current_a is None: 
                    current_a = headB
                if current_b is None: 
                    current_b = headA
    

Log in to reply
 

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