```
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
```

- O(n^2)time and O(1) space: it's straight
- 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. - 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.