使用 Python 以螺旋顺序打印单链表

什么是单向链表？

数据元素可以存储在非连续的内存位置的有序集合中的线性数据结构称为单向链表。它包含两个部分：数据部分和地址部分。节点的数据部分包含其信息，地址部分包含元素的地址。每个元素仅通过指针连接到下一个元素的下一个元素的数据部分。它只能单向遍历。每个节点只有一个next指针，因此无法反向遍历。

问题陈述

我们有一个链表。我们需要以螺旋顺序打印单向链表，这意味着它必须从中间开始并顺时针旋转。

让我们通过几个例子来理解这个问题陈述。

示例 1

输入

输出

7 - > 2 - > 4 - > 1 - > 5 - > 6

说明

我们需要以螺旋顺序打印链表，即它必须从中间元素开始然后顺时针移动。由于它有偶数个元素，我们需要决定中间元素。我们已将7作为中间元素。它将是螺旋单向链表的第一个元素。然后，它移动到相邻元素，即2。然后，顺时针移动，它将按此顺序移动：4、1、5，然后是6。

示例 2

输入

输出

13 - > 29 - > 44 - > 10 - > 23

说明

再次，在这个链表中，我们需要以螺旋顺序打印它。由于链表中存在奇数个元素，因此中间元素将是13。从13开始，它将按29、44、10，然后是23的顺序顺时针移动。

打印单向链表螺旋顺序有不同的方法。

1. 朴素方法

这是以螺旋顺序打印单向链表的最简单方法。在这种方法中，我们将在数组中存储链表数据，然后按螺旋顺序遍历其元素，然后打印出来。

此方法的基本算法

• 首先，创建一个数组。
• 然后，遍历链表。
• 将数据添加到数组中。
• 再次，使用两个指针以螺旋顺序遍历它。一个指针从中间元素指向左侧元素，第二个指针从中间元素指向结束元素。

2. 反向遍历方法

这是以螺旋顺序打印单向链表更有效且简单的方法。首先，我们将找到链表的中间元素，然后将其从起始元素到中间元素反转。然后，我们将从中间元素到起始元素反向遍历它。最后，从中间元素到结束元素正向遍历。

此方法的基本算法

• 首先，找到列表的中间元素以开始螺旋列表。
• 然后，反转从起始到中间元素的列表，以便反向遍历。
• 现在，使用两个指针遍历列表。一个指针用于中间元素，向左移动，另一个指针用于中间元素（mid + 1）的下一个元素，向右移动。

让我们使用 Python 实现将链表转换为螺旋顺序的代码

代码

输出

Linked List (even elements) :
5 --> 4 --> 7 --> 2 --> 1 --> 6 
Spiral Linked List (even elements) :
2 --> 7 --> 1 --> 4 --> 6 --> 5 
Linked List (odd elements):
23 --> 44 --> 13 --> 29 --> 10
Spiral Linked List (odd elements) :
13 --> 29 --> 44 --> 10 --> 23 

说明

使用此代码，我们打印了奇数和偶数个节点的链表螺旋顺序。首先，我们创建了一个 LinkedList 类并向其中插入了节点。然后，借助指针，我们创建了一个名为 Spiral() 的函数，该函数将链表转换为螺旋顺序。然后，使用 display() 函数，我们打印了螺旋链表。