首页pta题库单链表逆转

pta题库单链表逆转

时间: 2025-04-22 17:42:15 浏览: 29

### PTA 题库中的单链表逆序算法在处理单链表的逆序操作时，通常有多种方法可以实现这一目标。下面介绍一种迭代的方法来完成单链表的反转。 #### 迭代法实现单链表逆序为了更好地理解如何实现单链表的逆序功能，先定义一个简单的节点类 `Node` 和相应的链表反转逻辑： ```python class Node: def __init__(self, data=None): self.data = data self.next = None def reverse_linked_list(head): prev = None current = head while current is not None: next_node = current.next # 记录下一个节点 current.next = prev # 反转当前节点指针指向 prev = current # 移动prev到当前节点位置 current = next_node # 移动current到下一节点继续循环 return prev # 新头结点为原列表最后一个非None节点即prev ``` 此代码片段展示了如何利用三个变量 (`prev`, `current`, `next_node`) 来逐步遍历并翻转整个链表的方向[^1]。对于更复杂的场景或者特定平台上的应用需求（比如PTA），可能还需要考虑额外的因素如内存管理、边界条件检查等。上述例子提供了一个基础框架，在实际编程练习中可以根据具体题目要求调整细节部分。 #### 测试用例创建一些测试数据可以帮助验证所编写的函数是否按预期工作: ```python # 创建测试链表: 1 -> 2 -> 3 -> 4 -> 5 head = Node(1) node_2 = Node(2); node_3 = Node(3); node_4 = Node(4); node_5 = Node(5) head.next = node_2; node_2.next = node_3; node_3.next = node_4; node_4.next = node_5; reversed_head = reverse_linked_list(head) # 打印结果应显示：5->4->3->2->1 while reversed_head: print(reversed_head.data, end=' ') reversed_head = reversed_head.next print() ``` 这段程序会输出经过反转后的链表元素序列。

阅读全文