pta函数题单链表逆置
时间: 2025-06-30 17:58:34 浏览: 1
### 单链表逆置函数的实现方法
在单链表逆置的过程中,主要思路是通过改变每个节点的 `Next` 指针方向来实现链表的反转。以下分别提供 C 语言和 Python 的实现方式。
#### C语言实现
以下是基于提供的 PTA 题目要求的单链表逆置函数实现:
```c
List Reverse(List L) {
if (L == NULL || L->Next == NULL) { // 如果链表为空或只有一个节点,则直接返回
return L;
}
PtrToNode prev = NULL; // 前驱节点指针
PtrToNode curr = L->Next; // 当前节点指针(跳过头结点)
PtrToNode next = NULL; // 后继节点指针
while (curr != NULL) {
next = curr->Next; // 保存当前节点的后继节点
curr->Next = prev; // 将当前节点的 Next 指向前驱节点
prev = curr; // 移动 prev 和 curr 指针
curr = next;
}
L->Next = NULL; // 头结点的 Next 置为 NULL
return prev; // 返回新的头结点
}
```
此代码实现了单链表的逆置功能[^1]。其中,`prev`、`curr` 和 `next` 分别用于记录前驱节点、当前节点和后继节点,从而完成指针方向的反转。
#### Python实现
Python 中可以通过定义一个类来模拟单链表结构,并实现逆置功能。以下是具体实现:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
def reverse_list(head):
if head is None or head.next is None: # 如果链表为空或只有一个节点,则直接返回
return head
prev = None # 前驱节点指针
curr = head # 当前节点指针
while curr is not None:
next_node = curr.next # 保存当前节点的后继节点
curr.next = prev # 将当前节点的 next 指向前驱节点
prev = curr # 移动 prev 和 curr 指针
curr = next_node
return prev # 返回新的头结点
```
在此实现中,`reverse_list` 函数通过迭代的方式将链表的每个节点的 `next` 指针指向其前驱节点,从而完成链表的逆置[^2]。
#### 示例运行
假设输入链表为 `5 -> 1 -> 3 -> 4 -> 5 -> 2`,经过逆置后输出结果为 `2 -> 5 -> 4 -> 3 -> 1 -> 5`。
---
###
阅读全文
相关推荐
















