Python O(n+m+max(m,n)), the code is not neat but readable,need someone improve


  • 0
    H
    class Solution(object):
        def getIntersectionNode(self, headA, headB):
            """
            :type head1, head1: ListNode
            :rtype: ListNode
            """
            if not headA or not headB: return None
            alen,blen = 0,0
            ta,tb = headA,headB
            while ta:
                ta = ta.next
                alen+=1
            while tb:
                tb = tb.next
                blen+=1
            tlen = abs(alen-blen)
            if alen>blen:
                ta = headA
                tb = headB
            else:
                ta = headB
                tb = headA
            while tlen>0:
                ta = ta.next
                tlen-=1
            while ta and tb:
                if ta==tb:
                    return ta
                ta=ta.next
                tb=tb.next
            return None

  • 0
    J

    I refactored your code. It's doing the same thing, just using less variables. It could probably be even shorter, trading off for readability.

    def get_len(node):
        i = 0
        while node:
            i += 1
            node = node.next
    
        return i
    
    class Solution(object):
        def getIntersectionNode(self, headA, headB):
            """
            :type head1, head1: ListNode
            :rtype: ListNode
            """
            if not headA or not headB:
                return None
    
            alen, blen = get_len(headA), get_len(headB)
            longest, shortest = headA, headB
    
            if blen > alen:
                shortest, longest = headA, headB
    
            for _ in xrange(abs(alen - blen)):
                longest = longest.next
    
            while longest and shortest:
                if longest == shortest:
                    return longest
    
                longest = longest.next
                shortest = shortest.next
    
            return None

  • 0
    H

    nice, your ans is better


Log in to reply
 

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