题目描述
输入一个链表,反转链表后,输出新链表的表头。
思路
首先针对普通的情况,这里建立两个指针,pre和cur,分别表示前一节点和当前节点。对于当前节点,先将cur的下一个节点保存起来,然后转换指针方向,把cur指向pre。然后整体向后移动,pre移动到cur,cur移动到事先保存的cur的原本的next。此时移动后cur并没有指向pre。当再次处理当前cur时,cur会指向pre。
第二步就是考虑特殊情况,
1 表头是空,直接返回空
2 整个链表只有一个节点,返回这一个节点
代码
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
if pHead is None:
return None
if pHead.next is None:
return pHead
pre = None
cur = pHead
while cur is not None: #A B->C 假设cur是B
temp = cur.next #temp: C
cur.next = pre #A <-B C
pre = cur# pre 移到B
cur = temp# cur移到C
if cur is None: #pre到了尾部,cur是空
return pre
网友评论