单链表反转：四种方法实现

单链表反转（逆置）是一种常见的链表操作，可以通过多种方法来实现。以下是四种常见的方法：

1. 迭代法

迭代法是通过遍历链表，逐个交换节点的前后指针来实现反转的。这种方法思路简单，容易理解，但需要额外的空间来存储临时节点。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def reverseList(head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

1. 递归法

递归法是通过递归地调用反转函数来实现反转的。这种方法避免了额外的空间开销，但需要注意递归深度过大的问题。

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

1. 双指针法

双指针法是通过使用两个指针，一个慢指针和一个快指针，来交换节点的前后指针实现反转的。这种方法时间复杂度为O(n)，空间复杂度为O(1)。

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    fast = slow.next
    slow.next = None
    while fast:
        temp = fast.next
        fast.next = slow
        slow = fast
        fast = temp
    return slow

1. 迭代法改进版（快慢指针）

迭代法改进版是利用快慢指针的思想，通过两个指针一次遍历链表，实现链表反转。这种方法避免了额外的空间开销，且时间复杂度为O(n)。在遍历过程中，快指针每次移动两步，慢指针每次移动一步，当快指针到达链表尾部时，慢指针刚好在倒数第二个节点。此时将慢指针指向None即可完成反转。然后，将快指针逐步向前移动并更新其下一个节点为慢指针，直到快指针移动到头部。最后返回快指针即可。

以上四种方法都可以实现单链表反转，各有优缺点。迭代法虽然需要额外的空间，但实现简单易懂；递归法避免了额外的空间开销，但需要注意递归深度过大的问题；双指针法时间复杂度为O(n)，空间复杂度为O(1)，是一种高效的方法；迭代法改进版利用快慢指针的思想，避免了额外的空间开销，且时间复杂度为O(n)。在实际应用中，可以根据具体情况选择合适的方法来实现单链表反转。