定义单链表的类,实现一个带头结点的单链表的逆置,并将逆置前后的单链表分别遍历输出。单链表中各结点的值和结点个数等自定。
时间: 2024-10-10 21:10:31 浏览: 33
首先,我们来定义一个带头节点的单链表的基本类,包括插入节点、删除节点以及获取链表长度等功能。这里假设`ListNode`为链表节点,包含一个整数值`val`和一个指向下一个节点的引用`next`:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class SinglyLinkedList:
def __init__(self):
self.head = None
# 插入节点
def insert(self, val):
if not self.head:
self.head = ListNode(val)
else:
cur_node = self.head
while cur_node.next:
cur_node = cur_node.next
cur_node.next = ListNode(val)
# 遍历并打印原链表
def print_list(self):
node = self.head
while node:
print(node.val, end=" -> ")
node = node.next
print("None")
# 逆置链表
def reverse_list(self):
prev = None
current = self.head
while current:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
self.head = prev
# 遍历并打印逆置后的链表
def print_reversed_list(self):
node = self.head
while node:
print(node.val, end=" -> ")
node = node.next
print("None")
```
接下来,你可以创建一个`SinglyLinkedList`实例,并对其进行操作:
```python
# 创建链表
my_list = SinglyLinkedList()
my_list.insert(1) # 插入节点1
my_list.insert(2)
my_list.insert(3)
my_list.print_list() # 输出:1 -> 2 -> 3 -> None
# 逆置链表
my_list.reverse_list()
# 打印逆置后的链表
my_list.print_reversed_list() # 输出:3 -> 2 -> 1 -> None
```
阅读全文