剑指offer（python）-题目15-反转链表******

题目描述
输入一个链表，反转链表后，输出新链表的表头。
链表是通过一个个节点组成的，每个节点都包含了称为cargo的基本单元，它也是一种递归的数据结构。它能保持数据之间的逻辑顺序，但存储空间不必按照顺序存储。
如图：

链表的基本元素有：

节点：每个节点有两个部分，左边部分称为值域，用来存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。
head:head节点永远指向第一个节点 tail: tail永远指向最后一个节点 None:链表中最后一个节点的指针域为None值

思路1：
因为链表是有head和tail，而他们是有一个方向的，因此我们想直接进行类似list[::-1]这种反转就不是太方便。在下面的算法中，我们通过将链表截断，而后再拼接的方式进行反转。

以{1,2,3}链表作为例子，来说明下面算法中while迭代的流程（手工debug…）

1.将{2,3}的地址指向给tmp
2.将last=None指向pHead.next，这个时候pHead链表就被截断了，pHead只剩下了1，因为他的下一步指向了None
3.将此时的pHead，也就是1指向给last,这时候last为{1}
4.将tmp={2,3}指向给pHead,此时这轮迭代结束，开启下一轮. 这时，pHead是{2,3}，last是{1}

5.将{3}指向给tmp
6.将{1}指向给pHead.next，也就是2的下一步值，因此这时候pHead就变成了{2,1}
7.将{2,1}指向给last
8.将{3}指向给pHead,此时这轮迭代结束，开启下一轮. 这时，pHead是{3}，last是{2,1}

9.将None指向了tmp
10.将{2,1}指向给pHead.next，也就是{3}的下一步值，这个时候pHead就变成了{3,2,1}
11.将{3,2,1}指向给last
12.将None指向给pHead,此时这轮迭代结束，while迭代结束。 这时pHead是{None},last是{3,2,1}
https://www.jianshu.com/p/e385d9c06672
根据下图，先给定一个空的链表newList，然后判断传入的链表head是不是空链表或者链表元素只有一个，如果是，直接返回就可以。如果不是，则对链表进行迭代，然后给一个临时变量temp存储head.next,然后改变head.next的指向newList,然后把head赋值给newList,接着让head等于临时变量temp，就这样一直迭代完整个链表，返回newList就可以

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        if not pHead or not pHead.next:
            return pHead
        last =None
        while pHead:
            tmp = pHead.next#将下一步的地址指向给tmp
            pHead.next=last#将一个新的链表指向给旧链表pHead，这个时候就把pHead截断了，只剩下前面的链表值
            last=pHead#将旧链表的地址指向给新链表
            pHead=tmp#将旧链表原来的下一步只指向给pHead
        return last

思路2：–递归

思路：假设链表为[1,2,3,4,5]先迭代到链表末尾5，然后从5开始依次反转整个链表
如下图所示，先迭代待最后一位5，并且设置一个新的节点newList作为反转后链表的头结点，由于整个链表反转后的头就是最后一个数，所以newList存放的一直是反转后的头结点的地址，将head指向的地址赋值给head->next->next指针，并且一定要记得让head->next
=NULL，也就是断开现在指针的链接，否则新的链表形成了环，下一层head->next->next赋值的时候会覆盖后续的值。依次反转。

class Solution:
    # 返回ListNode
    def ReverseList(self, head):
        if head==None or head.next==None:
            return head
        newlist=ReverseList(head.next)
        head.next.next=head
        head.next=None
        return newlist