Python 程序以相反的顺序打印双向链表

在本教程中，我们将编写 Python 程序来打印反转的链表。双向链表是一种循环链表，用于创建循环链表。为了解决这个问题，我们将遵循以下步骤 -

• 使用指针遍历链表
• 交换所有节点的 prev 和 next 指针
• 最后，更改双向链表的头指针

示例 -

输出 -

Print Doubly Linked list 
Nodes of doubly linked list: 
4
2
8
1
5
12
Print Reversed Doubly Linked List
12
5
1
8
2
4

解释 -

在上面的代码中，我们创建了 Node 类，它初始化了单向链表。为了创建双向链表，我们初始化了双向链表类，其中我们将 head、prev 和 next 的初始值以及 count 的初始值都设置为 none 和零。我们定义了 insert_element() 函数，它调用 Node 类来插入元素。首先，我们检查 head 是否为 none，然后将新项插入到 head，并将 head 分配给 tail。

否则，我们将 tail 分配给 new_item.pre，将 new node 分配给 tail.next 和 tail。我们在每次插入元素时将 count 加一。

在 reverse() 函数中，我们将 current 变量设置为保存列表的 head。我们检查双向链表是否非空，然后我们将 current 的 next 存储到 temp 变量中，遍历双向链表，将 current 的 prev 分配给 current 的 next，并将 temp 分配给 current 的 prev。

在代码的最后，我们创建了 Doubly_Linked_List 类的对象，并将元素插入到列表中。我们调用 print_list() 方法来打印简单的双向链表，并调用 reverse() 函数来打印链表的反转。

时间复杂度为 O(N)，其中 N 代表双向链表中节点的数量，辅助空间为 O(N)。

使用堆栈反转双向链表

我们也可以使用堆栈来反转链表。我们将遵循以下方法 -

• 首先，我们遍历链表并将节点的数据推入堆栈。
• 然后，不断地从堆栈中弹出元素并更新双向链表。

下面将上述方法实现为 Python 代码 -

示例 -

输出 -

Print Doubly Linked list 
Nodes of doubly linked list: 
4
2
8
1
5
12
Print Reversed Doubly Linked List
12
5
1
8
2
4

时间复杂度为 O(N)，辅助空间为 O(N)。