876. middle of the linked list

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def (self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pt = head
count = 0
while pt != None:
pt = pt.next
count+=1
mid = count / 2 if count%2 == 0 else (count-1)/2
pa = head
countTwo = 0
while countTwo < mid:
pa = pa.next
countTwo+=1
return pa

Time complexity: O(1.5n)
Space Complexity: O(1)

loop through all node once to find index of middle node
loop second time to find the node at middle index

Best Answer

reduce time complexity

1
2
3
4
5
6
7
def middleNodeQuicker(self,head):  
pfast = head
pslow = head
while pfast != None and pfast.next != None:
pfast = pfast.next.next
pslow = pslow.next
return pslow

Time complexity: O(0.5n)
Space Complexity: O(1)

have fast pointer go two node each time, so it will tun 1/2 n time
the slow pointer will go one node each time and stop at mid node