用python介绍4种常用的单链表翻转的方法小结

1. 前言

单链表是一种常用的数据结构，其定义起来很简单：

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

其中，val 表示节点存储的数值，next 表示该节点的下一个节点。

本文将介绍四种常用的单链表翻转的方法，分别是：迭代翻转、递归翻转、头插法翻转和栈翻转。

2. 迭代翻转

迭代翻转的思路是，从头结点（即链表的第一个节点）开始，依次将每个节点插入到新链表的头部。

具体实现可以使用两个指针，分别指向当前节点和前一个节点，用一个临时变量保存当前节点的下一个节点，然后将当前节点插入到新链表的头部。

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    cur, pre = head, None
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return pre

在这里，我们需要注意两点。一是，要判断链表是否为空；二是，要在循环结束后返回新链表的头结点。

3. 递归翻转

递归翻转的思路是，先递归到链表的最后一个节点，然后依次将当前节点插入到它的后面。

具体实现可以用递归函数来实现，先递归到链表的最后一个节点，然后将当前节点插入到后面。

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

在这里，我们需要递归到链表的最后一个节点，然后将当前节点插入到它的后面。在最后一个节点时，直接返回它，它将会成为新链表的头结点。

4. 头插法翻转

头插法翻转的思路是，依次将链表中的每个节点插入到新链表的头部。

具体实现可以用一个临时变量存储当前节点的下一个节点，然后将当前节点插入到新链表的头部。

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

在这里，我们需要注意，在循环结束后，返回新链表的头结点。

5. 栈翻转

栈翻转的思路是，依次将链表中的每个节点入栈，然后依次弹出栈顶元素，组成新的链表即可。

具体实现可以用一个栈来存储链表中的每个节点，然后依次弹出栈顶元素，组成新的链表。

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    stack = []
    while head:
        stack.append(head)
        head = head.next
    dummy = ListNode(None)
    tail = dummy
    while stack:
        node = stack.pop()
        tail.next = node
        tail = tail.next
    tail.next = None
    return dummy.next

在这里，我们需要注意，在循环结束后，要将新链表的最后一个节点的 next 指针置为 None。

6. 总结

本文介绍了四种常用的单链表翻转的方法，分别是迭代翻转、递归翻转、头插法翻转和栈翻转。它们分别有各自的优缺点，可以根据具体情况选择不同的方法来解决问题。