160 intersection of two linked lists

AC and Best Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def (self, headA, headB):
"""w
:type head1, head1: ListNode
:rtype: ListNode
"""
if headA == None or headB == None:
return None
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:
return None
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 != None and pbb != None:
if paa.val == pbb.val:
return paa
paa = paa.next
pbb = pbb.next
return None

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