206. Reverse Linked List (Easy)

• 第一遍开始刷题，只用了一种方法，后面会补充一题多解。
• 思路一：迭代，我看好多评论都用迭代的方法，自己理解不来，学习了一下迭代。
  最后我的理解是：用的是迭代的思想，方法是链表的头插法。
  迭代思想：为了解决一个“大”问题，根据现实逻辑，如果能够找到同类问题的一个“最小问题”的答案（通常是已知的），并且根据已知算法，又可以因此得到比最小问
  题“大一级”问题的答案。
  而且，依次类推，又可以得到再大一级问题的答案，最终就可以得到“最大那个问题”（即要解决的问题）的答案。该思想的过程依赖与2个条件：
  1. 可知同类最小问题的答案；---头插法可以每次逆序一个
  2. 大一级问题的答案可以通过小一级问题的答案经过简单运算规则而得到。
  - 此思想的解体思路是：从小到大
  - 对比：递归思想是：从大到小，在回归到大。
• 思路二：递归

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre_node = None      # 头插法 1.创建一个新的节点，指针域置为空
        p = head    
        while (p != None):
            q = p.next
            p.next = pre_node # 头插法 2.将p的next域置为空---p的next域存放 pre_node 的地址     
            pre_node = p      # 头插法 3. pre_node next存放p的地址（pre_node指向p）
            p = q               
        return pre_node