有一个单链表 L(至少有 1 个节点),其头节点指针为 head,编写一个函数将 L 逆转,即最后一个节点变成第一个节点,原来倒数第二个节点变成第二个节点,如此等等。
时间: 2024-06-16 14:05:25 浏览: 44
要将单链表逆转,可以使用三个指针来实现。具体步骤如下:
1. 初始化三个指针:prev、current 和 next,分别指向前一个节点、当前节点和下一个节点。
2. 遍历链表,将当前节点的 next 指针指向前一个节点,然后更新 prev、current 和 next 指针。
3. 当遍历到最后一个节点时,将最后一个节点的 next 指针指向前一个节点,完成链表逆转。
4. 更新头节点指针 head,使其指向逆转后的链表的第一个节点。
下面是具体的代码实现:
```cpp
void reverseLinkedList(Node* &head) {
if (head == nullptr || head->next == nullptr) {
return; // 链表为空或只有一个节点,无需逆转
}
Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;
while (current != nullptr) {
next = current->next; // 保存下一个节点
current->next = prev; // 将当前节点的 next 指针指向前一个节点
prev = current; // 更新 prev 指针
current = next; // 更新 current 指针
}
head = prev; // 更新头节点指针
}
```
阅读全文