设有一个表头指针为 h 的单链表。试设计一个算法,通过遍历一趟链 表,将链表中所有结点的链接方向逆转,如图2.2所示。要求逆转结果链 表的表头指针 h 指向原链表的最后一个结点
时间: 2024-09-20 15:02:07 浏览: 80
要实现这个功能,你可以按照以下步骤设计算法:
1. 定义两个指针,`prev` 和 `current`,初始化时,`prev` 设置为 `NULL`,`current` 设置为链表的头节点 `h`。
2. 创建一个新的临时指针 `next`,用于存储 `current` 的下一个节点。
3. 开始遍历链表:
```python
while current is not None: # 当 current 不为空时
temp = current.next # 备份 current 的下一个节点
current.next = prev # 更新 current 的下一个节点为 prev(即将其反向)
prev = current # 移动 prev 到 current
current = temp # 移动 current 到下一个节点
```
4. 链表遍历结束后,链表的头节点 `h` 就变成了原链表的尾节点,所以最后更新 `head` 为 `prev`。
这是基于伪代码的Python实现,但请注意,这里的语法是Python,如果你是在C/C++环境中,会有所不同。以下是C++版本的代码实现:
```cpp
void reverseList(Node* &h) {
Node* prev = nullptr;
Node* current = h;
// 遍历链表
while (current != nullptr) {
Node* nextTemp = current->next;
current->next = prev;
prev = current;
current = nextTemp;
}
// 更新头节点为原链表尾节点
h = prev;
}
```
其中,`Node*` 是链表节点的定义,`&h` 表示传入的链表头指针的地址。
阅读全文