题解 | #链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
ListNode *dummy=new ListNode(0);
dummy->next=head;
ListNode *pre=dummy,*p=dummy->next;
int n=0;
while(p){ //遍历链表计算链表长度
++n;
p=p->next;
}
int r=n/k; //计算需要翻转几组
p=dummy->next;
while(r>0){ //翻转r组
for(int i=0;i<k-1;++i){ //k个节点为一组翻转链表，头插法
ListNode *temp=p->next;
p->next=temp->next;
temp->next=pre->next;
pre->next=temp;
}
pre=p; //更新需要翻转的中间部分的头节点
p=p->next; //更新需要翻转的第一个节点指针
--r;
}
return dummy->next; //时间复杂度O(n),空间复杂度O(1)
}
};
