头插法实现单链表逆置 数据结构C++版
时间: 2024-09-22 18:01:20 浏览: 41
头插法(即反转链表)是指通过在新链表的头部插入元素,逐步构建新的逆序链表。以下是使用C++实现单链表逆置的一种方法:
```cpp
#include <iostream>
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 使用头插法逆置链表
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) { // 特殊情况:空链表或只有一个节点
return head;
}
ListNode* prev = nullptr; // 初始化前驱节点为NULL
ListNode* curr = head; // 当前节点初始化为头节点
// 遍历链表,直到最后一个节点
while (curr != nullptr) {
ListNode* nextTemp = curr->next; // 保存当前节点的下一个节点
curr->next = prev; // 将当前节点的next指向前驱节点
prev = curr; // 移动前驱节点到当前节点
curr = nextTemp; // 移动当前节点到下一个节点
}
return prev; // 返回逆序后的头节点
}
// 打印链表
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != nullptr) {
std::cout << temp->val << " -> ";
temp = temp->next;
}
std::cout << "nullptr\n";
}
int main() {
// 创建一个示例链表
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
std::cout << "Original List: ";
printList(head);
head = reverseList(head); // 逆置链表
std::cout << "Reversed List: ";
printList(head);
return 0;
}
```
在这个例子中,我们先检查链表是否为空或只有一个节点,如果是则直接返回。接着,我们通过三个指针prev、curr和nextTemp,分别表示前驱、当前和原始的下一个节点。在每次循环中,我们将curr的next指向前驱节点,然后移动prev和curr。当遍历完整个链表后,prev就是新的头节点。
阅读全文