# Python solution with some thoughts analysis

•    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.

• 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

• This post is deleted!

• That's a nice thought

• @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

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