206. Reverse Linked List

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        pre = None
        cur = head
        temp = head.next
        while(temp):
            cur.next = pre
            pre = cur
            cur = temp
            temp = temp.next
        
        cur.next = pre
        return cur

Notes:

1. Check every corner cases, bother head.next and even head at the beginning

2. When there are multiple pointers in the linked list, always use the fastest one at looping criterion.

This problem could be solved by using only O(2) instead O(3) space. By using head, head.next and head.next.next. But this time, we don't need to redirect head.next.next to head, instead, we using head.next to store the head.next.next node, and insert the original head.next at the beginning of the list.