# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None:
return None
new_head = None
def dfs(node):
if node.next is None:
nonlocal new_head
new_head = node
return node
new_node = dfs(node.next)
node.next = None
new_node.next = node
return node
dfs(head)
return new_head
迭代
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
slow, fast = None, head
while fast is not None:
new_fast = fast.next
fast.next = slow
slow = fast
fast = new_fast
return slow