单链表分段逆转:给定一个带头结点的单链表和一个整数K,要求将链表中的每K个结点做一次逆转。(代码后面标注注释)
时间: 2024-06-13 10:05:12 浏览: 145
单链表分段逆转是指将一个带头结点的单链表中每K个结点进行逆转,具体实现可以按照以下步骤进行:
1. 定义一个函数,函数接收两个参数:链表头结点指针head和分段长度K。
2. 定义一个指针pre,用于记录每一段的前驱结点。
3. 定义一个指针cur,用于记录当前处理的结点。
4. 定义一个指针next,用于记录当前结点的下一个结点。
5. 定义一个计数器count,用于记录当前处理的结点数。
6. 遍历链表,对于每个结点执行以下操作:
1)将当前结点的下一个结点保存到next指针中;
2)如果count mod K等于1,说明当前结点是一段的第一个结点,需要将pre指针指向当前结点;
3)如果count mod K大于1,说明当前结点不是一段的第一个结点,需要将当前结点的next指针指向pre指针;
4)将pre指针指向当前结点;
5)将当前结点指针cur指向next指针。
7. 返回链表头结点指针head。
具体实现代码如下(C++实现):
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* pre = NULL;
ListNode* cur = head;
ListNode* next = NULL;
int count = 0;
ListNode* p = head;
int len = 0;
while (p) {
len++;
p = p->next;
}
ListNode* dummy = new ListNode(0);
dummy->next = head;
pre = dummy;
while (cur) {
count++;
next = cur->next;
if (count % k == 1) {
pre = cur;
} else if (count % k == 0) {
ListNode* tail = pre->next;
pre->next = next;
while (tail->next != next) {
ListNode* tmp = tail->next;
tail->next = tmp->next;
tmp->next = pre->next;
pre->next = tmp;
}
pre = tail;
}
cur = next;
}
return dummy->next;
}
};
```
阅读全文
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20250102104920.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)
![cpp](https://img-home.csdnimg.cn/images/20250102104920.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20241231044833.png)
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)