1.题目

原题

反转一个单链表。

例子

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

2.解析

这道题至少有四种解法，为了锻炼自己，我决定每个写法都写一下。

2.1最传统写法

改变链表的指针指向。这个需要对链表有一个比较深的理解。

链表是可以整体赋值给另外一个链表的，不必非想着用val，next构造链表。
链表的next赋予一个临时变量以后，这个链表就只有头部节点啦。
python里的旧链表赋值给新链表后，新链表值改变，旧链表也改变了。

2.2 队列写法

队列写法需要遍历两次，关键是要生成一个tmp链表，指向新链表

考虑链表生成，如果直接用next指向和更新的时候，其实，在赋值的时候就已经改变了链表的指向，所以需要保存一个新链表，让他保留原有值。
链表生成，要更新一个节点，不能直接用val写。

2.3原链表的操作

原链表操作的关键是要定义一个pre/cur/next，这样不用开辟一个新链表空间，直接就在原链表上操作。

还是老问题，next = head.next的时候，head就剩一个头部节点了
定义新链表，最后一个指针指向0

2.4递归写法

递归是真难写啊，首先要了解递归是啥。
递归：问题可以分解为子问题，要有一个公式的推导形式，比如求阶乘，f(n)=n!不叫公式推导形式，而f(n)=n*f(n-1)才是推导形式。那么递推要求以下两点：

要有一个推导公式，大问题可以拆分为可以分解的小问题
要有一个终止条件，要让程序知道从哪开始退出
关于递归的执行思路，这篇文章讲的很好，如果你不会递归看他。
递归的执行思路一言以蔽之：
顺序执行程序，遇到递归的位置，就从头开始走，递归退出了，就返回上次的断点，继续执行，就是递和归的过程。
那么链表翻转的递归思路是啥，1->2->3->4的翻转可以分解为1->2->3等子问题。那么递归，首先是要找到最后一个元素的位置。
然后依次连接回去，为了防止循环链表的出现，还要对head的next进行一个断开。

3.python代码

##传统解法：
class Solution:
    def reverseList(self, head):
        if head is None or head.next is None:
            return head#空链表和只有一个值的链表，直接输出原链表
        newarray = None
        tmp = None
        while head:
            tmp = head.next
            head.next = newarray
            newarray = head
            head = tmp
        return newarray
##队列写法
    def reverseList(self, head):
        if head is None or head.next is None:
            return head
        p = ListNode(0)
        p.next = head
        quene = []
        newarray = ListNode(0)
        tmp = newarray
        while p.next:
            quene.append(p.next.val)
            p = p.next
        # print(quene)
        for i in range(len(quene)):
            tmp.next = ListNode(quene.pop())
            tmp = tmp.next
        return newarray.next
##原链表操作
    def reverseList(self, head):
        if head is None or head.next is None:
            return head
        pre = None
        next = None
        cur = head
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre
#递归解法
    def reverseList(self, head):
        if head is None or head.next is None:
            return head
        new = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new