Concise python code with comments


  • 78
    I
    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

  • 0
    D

    Such an elegant solution! Bravo.


  • 0
    J

    So beautiful python solution! wow!


  • 0
    H

    brilliant! Thanks for the solution.


  • 0
    G

    Great Job! It runs faster than other py codes.


  • 0
    T

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


  • 0

    what a excellent method!


  • 4
    C

    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

  • 0
    Z

    Wow!!! quite good!


  • 8
    Z

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


  • 1
    V

    @zzl0 Me too, don't know why


  • 0
    T

    So brilliant!


  • 1

    Memory Limit Exceeded


  • 2
    M

    @zzl0

    Make the following changes would solve MLE.

    1. Add import gc
    2. 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
    

  • 0

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


  • 0
    Z

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


  • 0
    Z
    This post is deleted!

  • 1
    U

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


  • 0
    Z

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


  • 1
    D

    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
    

Log in to reply
 

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