用C++设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间
时间: 2024-10-01 08:11:03 浏览: 50
C++冒泡算法排序和链表中的应用
在C++中,你可以使用迭代的方式,通过三个指针`prev`, `current`, 和`next`来实现单向链表的反转。这里是一个简单的算法:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr; // 初始化前驱节点为空
ListNode* current = head; // 初始化当前节点为头节点
// 当链表非空时,遍历并更新指针
while (current != nullptr) {
ListNode* nextTemp = current->next; // 保存当前节点的下一个节点
current->next = prev; // 将当前节点指向前驱
prev = current; // 更新前驱为当前节点
current = nextTemp; // 更新当前节点为下一个节点
}
return prev; // 返回新的头节点,即原来的尾节点
}
```
这个算法的工作原理是每次迭代都改变当前节点的`next`指向前一个节点,直到遍历到链表的末尾。最后返回`prev`作为新链表的头节点。
阅读全文