几种单向链表翻转实现方法

除了迭代实现，单向链表还可以用递归和栈两种数据结构实现翻转。下面分别介绍这三种方法的实现。

### 迭代实现

迭代实现是将当前节点的指针指向前一个节点，然后移动三个指针，继续遍历下一个节点，最后将链表头节点指向当前节点，完成翻转。

def reverseList(head: ListNode) -> ListNode:
    prev, cur = None, head
    while cur:
        next_node = cur.next
        cur.next = prev
        prev = cur
        cur = 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

### 栈实现

栈实现的思路是将链表中的节点依次入栈，然后依次出栈，重新构建链表。

def reverseList(head: ListNode) -> ListNode:
    stack = []
    while head:
        stack.append(head)
        head = head.next
    new_head = ListNode(0)
    cur = new_head
    while stack:
        node = stack.pop()
        cur.next = node
        cur = cur.next
    cur.next = None
    return new_head.next

这三种方法的时间复杂度都是O(n)，但是递归实现的空间复杂度是O(n)，可能会存在栈溢出的风险。而迭代和栈实现的空间复杂度是O(1)，更加稳定。