设计一个算法,逆转一个链表的链接方向
时间: 2024-08-12 14:08:07 浏览: 56
逆转交替合并两个链表的解析与实现
逆转一个链表的链接方向是一个常见的链表操作,通常使用迭代或递归的方法来实现。这里提供一个使用迭代方法的算法:
**迭代法逆转链表:**
1. **定义三个指针**:
- `prev`(前一个节点),初始化为`nullptr`,用于存储当前节点的前一个节点;
- `current`(当前节点),初始化为链表头节点;
- `next_temp`(临时下一个节点),初始化为`nullptr`,用于暂存`current`节点的下一个节点。
2. **遍历链表**:
- 当`current`不为`nullptr`时,执行以下步骤:
a. 将`current`的`next`指针指向`prev`,逆转了`current`节点的链接;
b. 更新`prev`为`current`;
c. 更新`current`为`current->next`,移动到下一个节点;
- 循环直到`current`变为`nullptr`,此时链表已经遍历完成。
3. **返回逆转后的头节点**:
- 最后,`prev`就是逆转后的链表的新头节点。
**伪代码示例:**
```python
function reverseLinkedList(head):
prev = None
current = head
next_temp = None
while current is not None:
next_temp = current.next # 保存当前节点的下一个节点
current.next = prev # 将当前节点的next指向前一个节点
prev = current # 更新前一个节点为当前节点
current = next_temp # 更新当前节点为下一个节点
return prev # 返回新头节点
```
阅读全文