206 reverse linked list

AC and Best Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
def (self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pointer = head
end = None
while pointer != None:
then = pointer.next
pointer.next = end
end = pointer
pointer = then
return end

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

use two pointer, fast pointer(pointer) always one step more than slow pointer(end)
store next node of fast pointer, let fast pointer point to slow pointer, then both pointer go to next