C++实现链表首尾指定长度对调
时间: 2024-11-25 14:11:18 浏览: 15
c++实现链表增删改查
5星 · 资源好评率100%
在C++中,链表头部和尾部指定长度的元素对调可以通过迭代或递归的方式实现。这里提供一种迭代的方法:
```cpp
#include <iostream>
using namespace std;
// 链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || !head->next || k <= 0) return head; // 如果链表为空或者k无效,直接返回
ListNode dummy(0); // 创建虚拟头节点,方便处理头结点
dummy.next = head;
ListNode* prev = &dummy, *start = nullptr, *end = nullptr;
for (int i = 0; i < k; ++i) { // 找到第一个循环组开始位置
end = start;
while (end->next && end->next->next) {
end = end->next->next;
}
if (!end->next) break; // 如果当前组不满k个元素,则直接结束
start = end->next;
end->next = nullptr; // 将当前组断开
}
ListNode* tail = start;
while (tail->next) {
ListNode* temp = tail->next; // 保存需要移动的部分
for (int i = k - 1; i >= 0; --i) {
tail->next = temp->next; // 将这部分向前移动
temp = tail->next;
}
tail = tail->next; // 移动尾部指针
}
if (start == &dummy) return head; // 如果没找到实际的循环,返回原链表
return dummy.next; // 返回新的链表头
}
void printList(ListNode* node) {
while (node) {
cout << node->val << " ";
node = node->next;
}
cout << endl;
}
int main() {
ListNode* list = new ListNode{1, new ListNode{2, new ListNode{3, new ListNode{4, new ListNode{5}}}}};
cout << "Original List: ";
printList(list);
int k = 3;
list = reverseKGroup(list, k);
cout << "Reversed K-Group List (k=" << k << "): ";
printList(list);
return 0;
}
```
这个程序首先找到长度为k的循环部分,并将其断开。然后,它通过两个指针从头开始逆序整个部分,实现了头尾对调。`main`函数中展示了如何创建一个简单的链表并应用这个函数。
阅读全文