C++如何实现链表原地逆序
时间: 2024-09-13 19:13:35 浏览: 15
在C++中实现链表原地逆序,通常需要调整链表中节点的指针方向,使之反向链接。这个过程不需要创建新的节点,只需要改变指针的指向即可。以下是基本的步骤和代码实现:
1. 初始化三个指针变量,`prev` 用来保存当前节点的前一个节点,默认为null;`current` 用来遍历链表,初始指向链表的第一个节点;`next` 用来临时保存下一个节点。
2. 遍历链表,对于当前节点,先暂时保存下一个节点,然后将当前节点的`next`指针指向前一个节点(即`prev`),然后更新`prev`和`current`指针。
3. 遍历完成时,`prev` 将会指向原链表的最后一个节点,此时将`current`更新为`prev`,因为`prev`现在是新链表的头节点。
4. 最后返回`current`作为逆序后链表的头节点。
代码示例(假设定义了链表节点结构体`ListNode`):
```cpp
ListNode* reverseLinkedList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
ListNode* next = nullptr;
while (current != nullptr) {
next = current->next; // 保存下一个节点
current->next = prev; // 当前节点指向前一个节点
prev = current; // 前一个节点后移
current = next; // 当前节点后移
}
return prev; // 新的头节点
}
```