# Concise python code with comments

• ``````class Solution:
# @param two ListNodes
# @return the intersected ListNode
if headA is None or headB is None:
return None

pa = headA # 2 pointers

while pa is not pb:
# if either pointer hits the end, switch head and continue the second traversal,
# if not hit the end, just move on to next
pa = headB if pa is None else pa.next
pb = headA if pb is None else pb.next

return pa # only 2 ways to get out of the loop, they meet or the both hit the end=None

# the idea is if you switch head, the possible difference between length would be countered.
# On the second traversal, they either hit or miss.
# if they meet, pa or pb would be the node we are looking for,
# if they didn't meet, they will hit the end at the same iteration, pa == pb == None, return either one of them is the same,None``````

• Such an elegant solution! Bravo.

• So beautiful python solution! wow!

• brilliant! Thanks for the solution.

• Great Job! It runs faster than other py codes.

• more than good. it is a superior idea to switch the pointers at the ends of strings

• what a excellent method!

• Your solution is amazing!!!

I modified it a bit to make it more concise

``````def getIntersectionNode(self, headA, headB):
while A!=B:
A = A.next if A else headB
B = B.next if B else headA
return A``````

• Wow!!! quite good!

• I submitted the same code, and got 'Memory limit'.

• @zzl0 Me too, don't know why

• So brilliant!

• Memory Limit Exceeded

• @zzl0

Make the following changes would solve MLE.

1. Add import gc
2. Invoke gc.collect()
``````import gc

class Solution(object):
"""
:rtype: ListNode
"""
return None

gc.collect()
while a != b:
a = a.next if a else headB
b = b.next if b else headA
return a
``````

• @myliu Thanks that works! Can you please explain more on why this will work?

• @myliu thanks for your solution. But I don't understand why it works, since the solution does not create reference cycles.

May be the tests have some reference cycles ?

• This post is deleted!

• @icrtiou What would the time and space complexity of this be?

• @utsavvakil The time complexity is O(n) since every element is visited at most twice, and the space complexity is O(1) since there are only constant number of variable needed.

• Beautiful codes! Can be even more concise. We dont really need to compare if headA is None or headB is None. If A and B are both None, we just return one of them. If only one of them is None, they will go into the while loop just like all the other linked lists that dont meet each other. So I modified the codes and make it more concise:

``````class Solution(object):