c++ 翻转链表,k个一组
时间: 2024-02-02 21:04:03 浏览: 35
题目描述:
给定一个链表,每k个节点为一组进行翻转。例如,给定链表1->2->3->4->5,k=2,则应返回2->1->4->3->5。请注意,你需要在不修改链表节点值的情况下完成此操作。
示例:
输入: 1->2->3->4->5, k = 2
输出: 2->1->4->3->5
思路:
这道题是链表的操作,我们可以用递归来实现,每次递归处理k个节点,翻转它们,返回翻转后的头节点,然后将它接到上一组的尾部。
具体实现:
首先,我们需要定义一个辅助函数reverse,用来翻转链表。它的实现方法是,用三个指针pre、cur、next来遍历链表,将cur的next指向pre,然后将三个指针往后移动一个节点,重复这个过程,直到遍历完整个链表。
接下来,我们可以定义一个递归函数,它的参数是链表头节点和k。如果链表的长度小于k,说明不需要翻转,直接返回头节点;否则,我们先翻转前k个节点,然后将它们的尾节点接到下一组翻转后的头节点,递归处理下一组节点。每次递归返回的是翻转后的头节点,最后将所有头节点连接起来即可。
代码实现:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverse(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while (cur != NULL) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* cur = head;
int cnt = 0;
while (cur != NULL && cnt != k) { // 找到第k+1个节点
cur = cur->next;
cnt++;
}
if (cnt == k) { // 如果找到了,就翻转前k个节点
cur = reverseKGroup(cur, k); // 递归处理下一组节点
while (cnt-- > 0) { // 将翻转后的头节点接到下一组节点的尾部
ListNode* next = head->next;
head->next = cur;
cur = head;
head = next;
}
head = cur;
}
return head;
}
};
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)