class Solution:
# @param two ListNodes
# @return the intersected ListNode
def getIntersectionNode(self, headA, headB):
if headA is None or headB is None:
return None
pa = headA # 2 pointers
pb = headB
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
Concise python code with comments



Make the following changes would solve MLE.
 Add import gc
 Invoke gc.collect()
import gc class Solution(object): def getIntersectionNode(self, headA, headB): """ :type head1, head1: ListNode :rtype: ListNode """ if not headA or not headB: return None gc.collect() a, b = headA, headB while a != b: a = a.next if a else headB b = b.next if b else headA return a


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


@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): def getIntersectionNode(self, headA, headB): p1, p2 = headA, headB while p1 != p2: p1 = headB if not p1 else p1.next p2 = headA if not p2 else p2.next return p1