在c++中使用头插法的算法思想,实现单链表的就地逆置(要求在原链表上进行)。
时间: 2024-09-21 21:10:29 浏览: 21
在 C++ 中,头插法的逆置单链表算法通常不需要创建新的链表,而是通过改变节点的指针指向,在原链表的基础上完成逆序。以下是基于头插法的就地逆置单链表的实现过程:
1. 首先,定义链表节点结构体:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
```
2. 创建两个临时指针,一个指向头节点(`prev`),另一个指向当前节点(`current`)。初始时,`prev` 指向 `nullptr`,`current` 指向 `head`。
3. 为了实现头插法,每次迭代都将 `current` 的下一个节点插入到 `current` 和 `prev` 之间。然后,移动 `prev` 到 `current`,`current` 到 `current->next`,直到 `current` 变为 `nullptr`。
```cpp
void reverseList(ListNode*& head) {
ListNode* prev = nullptr;
ListNode* current = head;
while (current != nullptr) {
// 将当前节点的 next 指向 prev
ListNode* nextTemp = current->next;
current->next = prev;
// 移动 prev 和 current 指针
prev = current;
current = nextTemp;
}
// 更新链表头指针
head = prev;
}
```
4. 最后,调用 `reverseList(head)` 函数即可逆置单链表。