创建一个带头结点的双链表,链表中元素随机排列,逆置该链表
时间: 2024-03-13 20:19:58 浏览: 28
好的,为您解答。
以下是创建带头结点的双链表,链表中元素随机排列,并逆置该链表的代码,供您参考。
```python
# 定义双向链表节点类
class Node(object):
def __init__(self, val=None):
self.val = val
self.next = None
self.prev = None
# 定义双向链表类
class DoubleLinkedList(object):
def __init__(self):
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
# 在链表尾部插入节点
def add_node(self, val):
node = Node(val)
node.next = self.tail
node.prev = self.tail.prev
self.tail.prev.next = node
self.tail.prev = node
# 随机生成链表元素并插入
def create_random_list(self, n):
import random
for i in range(n):
val = random.randint(1, 100)
self.add_node(val)
# 反转链表
def reverse_list(self):
cur = self.head.next
while cur != self.tail:
cur.next, cur.prev = cur.prev, cur.next
cur = cur.prev
self.head.next, self.tail.prev = self.tail.prev, self.head.next
self.head.next.prev = self.head
self.tail.prev.next = self.tail
# 打印链表所有节点的值
def print_list(self):
cur = self.head.next
while cur != self.tail:
print(cur.val, end=' ')
cur = cur.next
# 在实际使用时,创建一个DoubleLinkedList对象,随机生成元素并插入,然后反转链表
if __name__ == '__main__':
dl = DoubleLinkedList()
dl.create_random_list(10)
print('原始链表:')
dl.print_list()
print('\n反转后的链表:')
dl.reverse_list()
dl.print_list()
```
其中,`create_random_list(n)` 方法可以创建一个 n 个元素的双向随机链表,`reverse_list()` 方法可以将链表反转。具体实现中将反转操作分成两步执行,首先将所有节点的 next 与 prev 交换,反转后 head 和 tail 的 next 与 prev 也需要调换。