1025python反转链表

可以使用迭代或递归来反转一个链表。

迭代方法：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    prev, curr = None, head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

递归方法：

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    new_head = reverseList(head.next)
    head.next.next = head
    head.next = None
    return new_head

这两种方法的时间复杂度都是 $O(n)$，空间复杂度是 $O(1)$ 或 $O(n)$（递归方法的空间复杂度是 $O(n)$）。