在 Python 中反转链表
Vaibhav Vaibhav
2022年5月18日
链表是计算机科学中的一种线性数据结构,它提供恒定时间的元素添加和删除。它由节点组成。
单个节点存储一些数据和下一个节点的地址。下一个节点存储它的数据和下一个节点的地址。单个节点只知道它指向的节点。它没有关于指向它的节点的信息。
这种结构允许我们在恒定时间内添加新节点和删除现有节点,给定它之前的节点,这与数组不同,我们必须将数组复制到新数组或移动数组的元素以创建添加和删除空间.
在数组中,可以借助索引在恒定时间内访问元素。但是对于链表,访问一个元素需要 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
如何变化。
previous |
current |
next |
---|---|---|
无 | 1 | 无 |
1 | 2 | 2 |
2 | 3 | 3 |
3 | 4 | 4 |
4 | 5 | 5 |
5 | 无 | 无 |
上面的表格单元格显示了节点存储的值。
Author: Vaibhav Vaibhav