在 Python 中反转链表

链表是计算机科学中的一种线性数据结构，它提供恒定时间的元素添加和删除。它由节点组成。

单个节点存储一些数据和下一个节点的地址。下一个节点存储它的数据和下一个节点的地址。单个节点只知道它指向的节点。它没有关于指向它的节点的信息。

这种结构允许我们在恒定时间内添加新节点和删除现有节点，给定它之前的节点，这与数组不同，我们必须将数组复制到新数组或移动数组的元素以创建添加和删除空间.

在数组中，可以借助索引在恒定时间内访问元素。但是对于链表，访问一个元素需要 O(n) 时间，其中 n 是链表的长度。

由于链表在结构上（线性）类似于数组，因此我们还可以对链表进行排序、过滤和搜索等操作。我们可以使用排序和搜索算法，例如冒泡排序、插入排序、归并排序、快速排序、选择排序、二分搜索和链表上的线性搜索。

本文将展示如何使用 Python 反转链表。请注意，代码片段考虑了一个代表链表块的 Node 类。

Node 类应如下所示。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

在 Python 中反转链表

参考以下 Python 代码在 Python 中反转链表。

def reverse(head: Node) -> Node:
    previous = None
    current = head
    next = None

    while current is not None:
        next = current.next
        current.next = previous
        previous = current
        current = next

    head = previous
    return head

要理解代码，请考虑一个示例链表，1 -> 2 -> 3 -> 4 -> 5 -> None。

首先，我们声明三个变量 previous、current 和 next，它们分别指向输入链表的头部 None 和 None。接下来，我们声明一个 while 循环，当 current 节点指向 None 时结束。

对于每次迭代：

• 我们将当前节点的下一个节点存储在下一个节点中。
• 将 current 节点的下一个节点设置为 previous 节点。
• 将 previous 节点重置为 current 节点。
• 将 current 节点重置为 next 节点。

下表表示当算法应用于上述示例时变量的值，即 previous、current 和 next 如何变化。

上面的表格单元格显示了节点存储的值。