在 Python 中反转链表

在本教程中，我们将编写 Python 语言反转链表的程序。链表用于动态存储元素。链表是一种线性的数据结构，类似于数组，但它以动态方式存储元素。每个元素通过特定的地址与其前面的节点连接，并存储值以及下一个元素的地址。整个元素称为节点。

在这里，我们将使用 Python 程序反转给定的链表。让我们来理解一下问题陈述。

问题陈述 -

我们需要提供链表并将其反转，如下所示。

让我们来实现给定问题的解决方案。

方法 - 1

首先，我们将创建链表并使用迭代方法解决此问题。

代码 - 创建链表

输出

1  -> 2  -> 3  -> 4  ->

在上面的代码中，我们初始化了链表并向其中添加了一些元素。现在，我们将实现反转链表的迭代方法。

反转链表

我们想要实现 reverse() 方法，它执行以下操作。

• 所有链接开始指向相反的方向。
• 头指针开始指向列表的最后一个元素。

我们将定义三个指针 -

• previous - 这是一个初始指针，开始时指向 None，该指针指向前一个元素，以便可以使用它来反转 next 链接。
• current - 它最初指向 head，此变量指向的节点将把 node.next 设置为列表中的前一个项。
• after - 它指向第二个节点。我们将此指针向前移动一个元素，直到它遇到 next==None。

让我们来实现 reverse_Llist() 函数。

示例 -

输出

The reverse linked list is: 
4  -> 3  -> 2  -> 1  ->

解释 -

在上面的代码中，我们初始化了链表实例并创建了链表。reverse_Llist() 函数被调用以反转列表。

方法 2 - 递归方法

输出

The reverse linked list is: 
4  -> 3  -> 2  -> 1  ->

时间复杂度：O(N)

辅助空间：O(1)

结论

在上面的教程中，我们实现了反转链表问题的解决方案。这是链表的一个重要概念，可能会在面试中被问到。我们已经使用迭代和递归方法解决了这个问题，并且两种方法的 time complexity 都是相同的。