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
Your solution is amazing!!!
I modified it a bit to make it more concise
def getIntersectionNode(self, headA, headB): if headA and headB: A, B = headA, headB while A!=B: A = A.next if A else headB B = B.next if B else headA return A
@zzl0 Me too, don't know why
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 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 ?
@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): 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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.