class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
pre = None
cur = head
while cur is not None:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
时间复杂度：O(n)
空间复杂度：O(1)
递归
# 从树的角度来看递归
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return self.recursive(head, None)
def recursive(self, cur, pre):
if cur is None:
return pre
tmp = cur.next
cur.next = pre
return self.recursive(tmp, cur) # 注意此时的return
class DListNode:
def __init__(self, val):
self.val = val
self.prev = self.next = None
def reverse(self, head):
cur = None
while head:
cur = head
head = cur.next
cur.next = cur.prev
cur.prev = cur
return cur