实现双向链表的逆置 C++完整代码
时间: 2024-09-09 21:14:52 浏览: 44
在C++中,我们可以使用迭代的方式来实现双向链表的逆置,因为只需要遍历链表一次即可。以下是完整的代码示例:
```cpp
#include <iostream>
// 定义双向链表节点结构体
struct Node {
int data;
Node* prev;
Node* next;
Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};
// 双向链表类
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
// 构造函数
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// 插入节点到链表尾部
void insert(int value) {
if (head == nullptr) {
head = tail = new Node(value);
} else {
Node* newNode = new Node(value);
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
// 逆置链表
void reverse() {
Node* current = head;
Node* temp = nullptr;
while (current != nullptr) {
temp = current->prev; // 保存当前节点的前驱节点
current->prev = current->next; // 更新当前节点的指向前驱为原后继
current->next = temp; // 更新当前节点的后继为原前驱
current = temp; // 移动到下一个节点
}
// 如果原始头节点未改变,则更新新头节点
if (temp != nullptr) {
head = temp->prev;
}
}
// 打印链表
void print() {
Node* temp = head;
while (temp != nullptr) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << "\n";
}
};
int main() {
DoublyLinkedList list;
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
std::cout << "Original List:\n";
list.print();
list.reverse();
std::cout << "Reversed List:\n";
list.print();
return 0;
}
```
在这个例子中,我们首先创建了一个双向链表并插入了一些元素。然后调用`reverse`方法来逆置链表,最后打印出逆转后的链表。