c++实现不带头单链表倒置用双指针
时间: 2024-09-28 11:03:25 浏览: 7
在 C++ 中,可以使用双指针法(也称为快慢指针法)来实现不带头结点的单链表的反转。这种方法通常涉及到两个指针,一个移动较快,每次前进两步,另一个移动较慢,每次前进一步。当快速指针到达链表的末尾时,慢速指针就指向了链表的中间位置。然后我们只需要将这两个指针所对应的节点进行交换,并分别让它们向后移动,直到慢速指针追上它,即可完成整个链表的反转。
以下是步骤和伪代码描述:
1. 定义两个指针 `prev` 和 `current`,初始化为 NULL 和头节点 `head`。
2. 当 `current` 不为空时,进入循环:
- 将 `prev` 设置为当前节点 `current` 的下一个节点(`prev = current->next`)。
- 将当前节点的 `next` 指针指向原来的前一个节点 (`current->next = prev`),实现了交换。
- 移动 `current` 到其下一个节点 (`current = current->next`)。
3. 循环结束后,`prev` 就是新链表的头节点,因为所有节点都已经被指向前一个节点了。
下面是简单的 C++ 代码实现:
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* current = head;
// 反转过程
while (current != nullptr) {
ListNode* nextTemp = current->next;
current->next = prev;
prev = current;
current = nextTemp;
}
return prev; // 返回新的头节点
}
```