23
04/2015
[LeetCode] Reverse Nodes in k-Group
Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
解题思路：
这道题花了我一下午的时间，必须面壁思过~
其实这道题包含了一个小问题，就是单链表的逆转问题，其想法是先扫描的节点放在后面，时间复杂度只需O（n），空间复杂度为O（1）。基于这个思想，我们稍作改动，即为该问题的解。
/**
* 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) {
if(head==NULL||k<=1){
return head;
}
ListNode* myHead=new ListNode(0);
myHead->next=head;
ListNode* last=myHead;
ListNode* pre=myHead;
while(true){
int i=0;
while(i<k&&last!=NULL){
last=last->next;
i++;
}
if(i<k||last==NULL){
break;
}
ListNode* partHead=pre->next;
pre->next=reverse(partHead, last);
pre=last=partHead;
}
head=myHead->next;
delete myHead;
return head;
}
//输入部分链表的头节点，和该部分链表的最后一个节点，返回倒转后该部分链表的头结点
ListNode* reverse(ListNode* head, ListNode* last){
if(head==last){
return head;
}
ListNode* current=head->next; //原链表的当前节点
ListNode* newHead=head; //新链表的头结点
newHead->next=last->next;
while(current!=last){
ListNode* temp=current->next;
current->next=newHead;
newHead=current;
current=temp;
}
current->next=newHead;
newHead=current;
return newHead;
}
};
0 条评论