206 Reverse Linked List

原题链接：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
        """
        newHead = None
        while head != None:
            nextNode = head.next
            head.next = newHead
            newHead = head
            head = nextNode
        return newHead

我们采取的方法是这样的，逐个反转每一个指针，
举个例子：
假设链表是这个样子的：head->1->2->3->4->None
那么在第一步结束后，链表应该是这个样子的：None<-head, 1->2->3->4->None
在第二步结束后，链表是这个样子的：None<-head<-1, 2->3->4->None
在第三步结束后，链表是这个样子的：None<-head<-1<-2, 3->4->None
以此类推。

那么我们现在来看具体的代码，以及尝试理解这些代码是如何做到上述的步骤的：

nextNode = head.next  #1
head.next = newHead  #2
newHead = head  #3
head = nextNode  #4

#1:这句代码是用来保存革命的火种。
因为假如我们直接反转了head.next的指向，那么head.next之前指向的内容（即链表在head这个节点后面的部分）都会丢失了。所以我们在反转第一个指针的指向之前，我们要保存一下它的值。

#2:这句代码就是反转指针的操作。
这个newHead就是用来装前一个节点的变量（其实它是前一个节点的引用，不过不要在意这些细节，我们主要是方便理解），
比如说，当我们反转head->1后，反转结果为None<-head, 1，此时newHead就是None；
当我们反转1->2后，反转结果为head<-1, 2，此时newHead就是head。

#3:反转指针之后，我们需要更新newHead的值，用于下一轮的反转。
这里我们要思考一下，为什么用head的值来更新newHead呢？
答：因为这一轮的head就是下一轮，指针反转后要被指向的节点，也就是newHead。

#4:这句代码主要是配合#1的代码。既然#1已经保存了革命的火种，那在下一轮即将开始之前，我们当然要将火种传递下去。
这里我们还要思考一下，为什么要传给head而不是newHead？
答：因为head指向的是尚未被反转的链表部分啊！而newHead指向的是已被反转的链表部分啊！

总结：
以上是用迭代方法原地反转单链表，至于递归的方法等有时间再写吧~~~