链表反转是一个常见的算法问题，通常用于考察对链表操作的理解。下面是反转单链表的基本思路和实现方法。
反转单链表的思路
使用三个指针：
prev：初始化为nullptr，用于存储已反转部分的尾节点。curr：初始化为头节点，用于遍历链表。next_temp：用于临时保存当前节点的下一个节点。
遍历链表：
- 在循环中，将当前节点的下一个指针指向前一个节点，然后更新指针，使其移动到下一个节点。
结束条件：
- 当
curr为nullptr时，说明遍历完了整个链表，此时prev就是新的头节点。
- 当
C++ 实现
#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr; // 初始化 prev 为 nullptr
ListNode* curr = head; // 当前节点从头开始
while (curr != nullptr) { // 遍历链表
ListNode* next_temp = curr->next; // 保存下一个节点
curr->next = prev; // 将当前节点的 next 指向前一节点
prev = curr; // 移动 prev 到当前节点
curr = next_temp; // 移动到下一个节点
}
return prev; // 返回新的头部（即原来的尾部）
}
};
// 辅助函数用来创建和打印链表（可选）
void printList(ListNode* head) {
while (head != nullptr) {
std::cout << head->val << " -> ";
head = head->next;
}
std::cout << "nullptr" << std::endl;
}
int main() {
// 创建测试用例: 1 -> 2 -> 3 -> nullptr
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
std::cout << "Original list: ";
printList(head);
Solution solution;
ListNode* reversedHead = solution.reverseList(head);
std::cout << "Reversed list: ";
printList(reversedHead);
return 0;
}
输出结果
运行上面的代码将输出：
Original list: 1 -> 2 -> 3 -> nullptr
Reversed list: 3 -> 2 -> 1 -> nullptr
总结
- 使用三个指针的方法能够有效地反转单链表，时间复杂度为 O(n)，空间复杂度为 O(1)。
- 确保在使用指针时处理好边界条件，以避免出现空指针异常。
内容由零声教学AI助手提供，问题来源于学员提问
