非递归与递归的方式:
非递归:
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
# @param head ListNode类
# @return ListNode类
# 非递归方式
class Solution:
def ReverseList(self , head: ListNode) -> ListNode:
# write code here
# 使用两个指针pre和cur
pre = None
cur = head
if not cur: # 头节点为空
return cur
else:
while cur: # 头节点不为空的时候,从头节点开始依次反转链表,循环至cur = None
temp = cur.next # temp存储当前节点的下一个节点
cur.next = pre # 反转,当前节点的下一个节点赋值为pre
pre = cur # pre变为当前节点,为一下赋值做准备
cur = temp # 将cur移动至下一个节点,即temp
return pre
递归
# 递归的方式
class Solution:
def ReverseList(self , head: ListNode) -> ListNode:
# 引入sys,避免超过最大递归深度的问题
import sys
sys.setrecursionlimit(1500)
def reverse(pre, cur):
if not cur:
return pre
else:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return reverse(pre, cur)
return reverse(None, head)