定义单链表的类,实现一个带定义单链表的类,实现一个带头结点的单链表的逆置,并将逆置前后的单链表分别遍历输出。单链表中各结点的值和结点个数等自定。 头结点的单链表的逆置,并将逆置前后的单链表分别遍历输出。单链表中各结点的值和结点个数等自定。
时间: 2024-10-10 08:10:32 浏览: 35
首先,我们可以定义一个`ListNode`类,代表单链表中的节点,包含一个数据元素和指向下一个节点的指针:
```python
class ListNode:
def __init__(self, data):
self.val = data
self.next = None
# 创建一个带头结点的单链表类
class DoublyLinkedList:
def __init__(self):
self.head = ListNode(0) # 初始化头结点
self.tail = self.head # 尾部默认指向头结点
self.length = 0 # 存储链表长度
# 添加节点到链表尾部
def append(self, data):
new_node = ListNode(data)
self.tail.next = new_node
self.tail = new_node
self.length += 1
# 逆置链表
def reverse(self):
prev = None
current = self.head
while current:
next_temp = current.next # 临时保存当前节点的下一个节点
current.next = prev # 转换方向,让当前节点指向前一个节点
prev = current # 更新前驱节点
current = next_temp # 移动到下一个节点
self.tail = self.head # 新的头结点变为原来的尾结点
# 遍历并打印链表
def traverse(self):
current = self.head
while current:
print(current.val, end=" -> ")
current = current.next
print("None")
# 遍历逆置后的链表
def traverse_reversed(self):
current = self.tail
while current is not None:
print(current.val, end=" -> ")
current = current.next
print("None")
```
在这个`DoublyLinkedList`类中,我们实现了链表的基本操作(添加节点、逆置链表以及遍历),你可以根据需要创建链表实例并测试逆置功能。
阅读全文