循环单链表倒置C++
时间: 2024-08-14 10:06:39 浏览: 33
循环单链表倒置是指将一个已知首节点的循环单链表中的元素顺序反转,保持原有的环状结构不变。在C++中,我们可以使用迭代或者递归的方式实现这个操作。这里是一个基本的迭代算法:
```cpp
class ListNode {
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseCycle(ListNode* head) {
if (!head || !head->next) {
return head; // 如果链表为空或只有一个元素,无需反转
}
ListNode *prev = nullptr, *fast = head, *slow = head;
while (fast && fast->next != slow) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
// 分割两个部分
if (!fast || fast == slow) { // 链表长度是偶数,或者只有一个循环
prev->next = nullptr; // 取消循环
return head;
} else {
prev->next = fast; // 将循环连接到快指针上
fast = head;
}
// 反转剩余部分
ListNode *newHead = reverseList(slow); // 从慢指针开始反向遍历并返回新的头
// 合并两个链表
fast->next = newHead;
newHead->next = slow; // 将反转后的链表接到循环链表的头部
return head;
}
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode *prev = nullptr, *curr = head, *next = nullptr;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)