给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例 :
给定这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
说明 : 你的算法只能使用常数的额外空间。 不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
给定这个链表:1->2->3->4->5,k=2
-1-反转操作,5->4->3->2->1
-2-跳过1个反转2个2个,5->3->4->1->2
-3-再反转一次,2->1->4->3->5
这种解法,细节很多,很容易出错。
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if(k == 1 || !head)
return head;
int len = 1, count;
ListNode *prev = NULL, *cur = head, *nt = head->next;
ListNode *H = reverseList(prev,cur,len);//反转后的表头
if(len == 1)
return head;
count = len/k;
len = len%k;//反转后,前几个(原末尾)不用反转的
bool flag = (len == 0);
prev = NULL, cur = H, nt = cur->next;
while(len--)
{
prev = cur;
cur = cur->next;
if(cur)
nt = cur->next;
}//前几个不用反转
if(prev)
prev->next = NULL;
ListNode *newhead;
while(count--)//后面count组需要反转
{
newhead = reverseKNode(cur,nt,k);//反转k个, cur、nt是引用
if(flag)//如果前面0个不用反转
{
H = newhead;//表头就是第一个反转后的表头
flag = false;
}
if(prev)
prev->next = newhead;
prev = cur;
cur = nt;
if(cur)
nt = cur->next;
}
cur = H, prev = NULL;
return reverseList(prev,cur,len);
}
ListNode* reverseList(ListNode *prev, ListNode *head, int& len)
{
ListNode *nt = head->next;
while(head && head->next)
{
len++;
head->next = prev;
prev = head;
head = nt;
if(nt)
nt = nt->next;
}
head->next = prev;
return head;
}
ListNode* reverseKNode(ListNode* &head, ListNode* &nt, int k)
{
ListNode *prev = NULL, *tail = head;//记录表尾
while(k--)
{
head->next = prev;
prev = head;
head = nt;
if(nt)
nt = nt->next;
}
nt = head;//下一段的开头nt
head = tail;//表尾引用出去
return prev;
}
};
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode *emptyHead = new ListNode(-1);
emptyHead->next = head;
ListNode *prev = emptyHead, *start = emptyHead->next, *end = emptyHead;
//start,end,对应k个节点的首尾,prev前一段的末尾
ListNode *temp=NULL;
bool flag = false;
int count;
while(end)
{
count = k;
start = prev->next;//前一段的下一个为start
while(end && count)//end移动k次到末尾
{
end = end->next;
count--;
}
if(!end)//如果end为空,说明,不够k个
flag = true;//这一段不足k个,提前结束了
else//够k个,需要反转
{
temp = end->next;//temp为下次反转的段的开头
end->next = NULL;//断开与下段的链接
}
if(!flag)//没有提前结束,这段够k个,进行反转
{
prev->next = reverseList(start);
//前一段的next接上新的头
start->next = temp;
//原来的头start变成尾巴,接上下一段的头temp
prev = start;//更新prev为反转好的尾巴start
end = start;//反转k个后,原来的end不是结尾了,end更新为新的结尾start
}
}
return emptyHead->next;
}
ListNode* reverseList(ListNode *head)
{ //反转链表,返回新的头结点
ListNode *prev = NULL, *nt = head->next;
while(head && head->next)
{
head->next = prev;
prev = head;
head = nt;
nt = nt->next;
}
head->next = prev;
return head;
}
};