首页给定一个带头结点的单链表和一个整数k,要求将链表中的每k个结点做一次逆转。输入一个整数L,一个长度为L的链表，一个整数k。 0<L<10000 0<k<=L 输出翻转后的链表。c++

给定一个带头结点的单链表和一个整数k,要求将链表中的每k个结点做一次逆转。输入一个整数L,一个长度为L的链表，一个整数k。 0<L<10000 0<k<=L 输出翻转后的链表。c++

时间: 2025-06-09 22:05:52 浏览: 14

在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 == 1) return head; ListNode* dummy = new ListNode(0); // 创建虚拟头节点 dummy->next = head; // 分隔前k-1个节点和剩余部分 ListNode* pre = dummy, *cur = head, *end = head + k - 1; // 反转k个节点 for (int i = 0; i < k && cur; ++i, ++cur) { pre->next = cur->next; cur->next = end->next; end->next = cur; pre = cur; } // 将剩余部分作为新的头节点 if (cur) { head = reverseKGroup(cur, k); } else { head = dummy->next; // 没有需要反转的部分，直接返回原链表 } return head; } ``` **迭代版本：** ```cpp ListNode* reverseKGroup(ListNode* head, int k) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* prev = dummy, *start = nullptr, *curr = head; while (curr) { // 找到第k个节点 for (int i = 1; i < k && curr; ++i) { curr = curr->next; } // 翻转子链表 ListNode* nextNode = curr->next; for (int i = k - 1; i >= 0; --i) { curr->next = prev->next; prev->next = curr; curr = nextNode; nextNode = curr->next; } // 更新起始位置 start = curr; prev = curr; curr = nextNode; } return dummy->next; } ``` 这两个版本的代码都会先找到k个节点，然后通过指针交换它们的位置，完成一次逆序操作，然后再继续处理下一个k个节点。

阅读全文