首先附上完整答案
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
- 将pHead的next指向上一个节点,last,这里last 初始值的None是反转后最后一个节点的next值
3.存储完之后在遍历到下一个节点之前需要将last改成制作完的当前节点,供下一个节点指向
最后改头节点,等遍历完后pHead等于None,last就是原来最尾巴的节点,将它返回即可,因为它就是头节点
特殊情况:传入的phead是空,或者是单独的node,则没有反转的必要直接返回phead就好
