在c++中使用头插法的算法思想,实现单链表的就地逆置(要求在原链表上进行)。试写一算法,定义为LinkList的成员函数实现
时间: 2024-09-22 10:05:21 浏览: 45
在C++中,头插法(也称为前向遍历)通常用于操作链表,尤其是当我们需要在原链表上逆置它时。这里提供一个简单的单链表逆置的算法,通过三个指针prev、current和next来实现链表的就地逆置:
```cpp
class LinkList {
public:
// 定义节点结构体
struct Node {
int data;
Node* next;
};
// 成员函数,头插法逆置链表
void reverseInPlace() {
if (head == nullptr || head->next == nullptr) { // 如果链表为空或只有一个元素
return;
}
Node* prev = nullptr; // 初始化prev为nullptr
Node* current = head; // 当前节点指向头节点
while (current != nullptr) { // 遍历链表
Node* nextTemp = current->next; // 保存当前节点的下一个节点
current->next = prev; // 将当前节点的next指向前一个节点
prev = current; // 更新prev为当前节点
current = nextTemp; // 更新current为下一个节点
}
head = prev; // 最后将新的头节点赋给head
}
private:
Node* head; // 链表头指针
};
阅读全文