141 linked list cycle

AC and Best Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
def (self, head):
"""
:type head: ListNode
:rtype: bool
"""
walk = head
run = head
while walk != None and run != None and run.next != None:
walk = walk.next
run = run.next.next
if walk == run:
return True
return False

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

use two pointer, fast pointer(pointer) go twise as fast as slow pointer
if fast pointer = slow pointer, means there is a cycle