链表反转

首先附上完整答案

class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        if not pHead or not pHead.next:
            return pHead
        last = None   #指向上一个节点
        while pHead:
            #先用tmp保存pHead的下一个节点的信息，
            #保证单链表不会因为失去pHead节点的next而就此断裂
            tmp = pHead.next   
            #保存完next，就可以让pHead的next指向last了
            pHead.next = last
            #让last，pHead依次向后移动一个节点，继续下一次的指针反转
            last = pHead
            pHead = tmp
        return last

第一步:我们要知道python怎么表示链表,我们知道链表是由节点(Node)组成,每个节点中存储自身的值和下一个节点的地址,一个完整的链表只需要存储头节点即可.
节点的结构如下:

class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

节点的制作过程:制作一个类,类中有两个属性,一个val一个next,val代表当前这个节点的值,next指向下一个节点本身

第二步:链表的反转需要做两件事
一、对于每个节点来说方向反转:原来每个节点的next是指向他的下一个节点,我们需要改成指向它的上一个节点,重点:反转
二、对于整理链表而言,需要遍历链条执行上一步操作,重点:遍历
三、需要将头节点改成原来最尾巴那个node

先考虑如何遍历:
比如pHead是原来的头节点:
while pHead:
pHead = pHead.next
这样就遍历完了

再考虑遍历过程中怎么反转:
1.我们需要先保留住pHead的当前状态值,即用一个tmp存pHead.next, tmp = pHead.next

2. 将pHead的next指向上一个节点,last,这里last 初始值的None是反转后最后一个节点的next值
   3.存储完之后在遍历到下一个节点之前需要将last改成制作完的当前节点,供下一个节点指向

最后改头节点,等遍历完后pHead等于None,last就是原来最尾巴的节点,将它返回即可,因为它就是头节点

特殊情况:传入的phead是空,或者是单独的node,则没有反转的必要直接返回phead就好