用C++将一个已知的单链表进行逆置运算,如(a1.2.….an) 变为(an ··a2, a1)。
时间: 2024-10-11 15:09:42 浏览: 23
在C++中,你可以使用迭代或递归的方式来反转一个单链表。这里是一个简单的迭代方法:
```cpp
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 函数来反转链表
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr; // 存储前一个节点
ListNode* current = head; // 当前节点
ListNode* nextTemp = nullptr; // 暂存当前节点的下一个节点
while (current != nullptr) {
// 将当前节点的下一个指针存储
nextTemp = current->next;
// 更新当前节点的指向
current->next = prev;
// 移动prev和current到下一个位置
prev = current;
current = nextTemp;
}
return prev; // 返回新的头节点
}
int main() {
// 创建一个示例链表
ListNode* list = new ListNode(1);
list->next = new ListNode(2);
list->next->next = new ListNode(3);
cout << "Original list: ";
printList(list); // 打印原链表
list = reverseList(list); // 反转链表
cout << "Reversed list: ";
printList(list); // 打印反转后的链表
return 0;
}
// 辅助函数打印链表
void printList(ListNode* node) {
while (node != nullptr) {
cout << node->val << " ";
node = node->next;
}
cout << endl;
}
```
在这个例子中,`reverseList`函数接受一个链表头节点,并通过不断地更新节点的next指针,实现了链表的逆转。
阅读全文