定义单链表的类,实现一个带定义单链表的类,实现一个带头结点的单链表的逆置,并将逆置前后的单链表分别遍历输出。单链表中各结点的值和结点个数等自定。 头结点的单链表的逆置,并将逆置前后的单链表分别遍历输出。单链表中各结点的值和结点个数等自定。

时间: 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`类中,我们实现了链表的基本操作(添加节点、逆置链表以及遍历),你可以根据需要创建链表实例并测试逆置功能。
阅读全文

相关推荐