def(self, headA, headB): """w :type head1, head1: ListNode :rtype: ListNode """ if headA == Noneor headB == None: returnNone countA = 0 countB = 0 pa = headA pb = headB while pa !=None: pa = pa.next countA+=1 while pb != None: pb = pb.next countB+=1 if pa != pb: returnNone paa = headA pbb = headB lengthDiff = max(countA,countB) - min(countA,countB) if countA < countB: countx = 0 while countx < lengthDiff and pbb != None: pbb = pbb.next countx+=1 elif countA > countB: countx = 0 while countx < lengthDiff and paa != None: paa = paa.next countx+=1 while paa != Noneand pbb != None: if paa.val == pbb.val: return paa paa = paa.next pbb = pbb.next returnNone
Time complexity: O (m+n) Space complexity:O (1)
first get length of each list and its last node, if last node not equal, means there is no intersection base on length, have a pointer on list longer, keep going until len(shorter) == len(longer from pointer) create two pointer pointer to two list, when two pointer have same value, return
近期评论