K个一组翻转链表

发布于:2021-09-28 17:27:50

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。


k 是一个正整数,它的值小于或等于链表的长度。


如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。


示例:



给你这个链表:1->2->3->4->5




当 k = 2 时,应当返回: 2->1->4->3->5




当 k = 3 时,应当返回: 3->2->1->4->5



/**
* 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* dummy = new ListNode(0);
dummy->next = head;
//思路:每一段每一段反转,找到每一段的前置结点、尾结点、开始的结点、结束结点的next
ListNode* pre = dummy; //前置结点
ListNode* end = dummy; //每个尾结点

while (end->next) {
for (int i = 0; i < k && end; i++) end = end->next; //找到是不是还有k个结点
if (end == NULL) break; //不够k个,循环结束

ListNode* start = pre->next;//倒置结点起始位置
ListNode* next = end->next;//记录next为end指向下一个结点的地址,作为下一次的起始位置
end->next = NULL;//end指向空的尾结点
pre->next = reverse(start);//开始倒置strat到end的结点

start->next = next; //start指向下一次的起始位置
pre = start; //pre为前置结点
end = start; //end为每个尾结点
}
return dummy->next;
}

ListNode *reverse(ListNode* head) {
ListNode* pre = NULL; //新链表头结点
ListNode* curr = head;
while (curr) {
ListNode *next = curr->next;
curr->next = pre;
pre = curr;
curr = next;
}
return pre;
}
};

相关推荐

最新更新

猜你喜欢