题目描述
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例:
给你这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
说明:
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
解题思路
找到每组链表节点的头和尾(head、tail),将这一组节点翻转;
另外,需要保留每组节点的上一个节点(prev、next),方便接上翻转后的头、尾节点;
对于第一组节点,由于没有prev,需要设定一个虚的prev节点(hair),另外这样也方便直接返回结果(hair->next)。
pair<ListNode*, ListNode*> helper(ListNode* head, ListNode* tail){
ListNode* prev = tail->next;
ListNode* curr = head;
while(prev!=tail){
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return pair<ListNode*, ListNode*>(tail, head);
}
ListNode* reverseKGroup(ListNode* head, int k){
ListNode* hair = new ListNode(0);
hair->next = head;
ListNode* prev = hair;
while(head){
ListNode* tail = prev;
for(int i=0; i<k; i++){
tail = tail->next;
if(!tail)
return hair->next;
}
ListNode* nex = tail->next;
tie(head, tail) = helper(head, tail);
prev->next = head;
tail->next = nex;
prev = tail;
head = nex;
}
return hair->next;
}
网友评论