有一個(gè)單鏈表家坎，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法疮茄，使得每K個(gè)節(jié)點(diǎn)之間逆序，如果最后不夠K個(gè)節(jié)點(diǎn)一組员咽，則不調(diào)整最后幾個(gè)節(jié)點(diǎn)毒涧。例如鏈表1->2->3->4->5->6->7->8->null，K=3這個(gè)例子贝室。調(diào)整后為契讲，3->2->1->6->5->4->7->8->null。因?yàn)镵==3滑频，所以每三個(gè)節(jié)點(diǎn)之間逆序捡偏，但其中的7，8不調(diào)整峡迷，因?yàn)橹挥袃蓚€(gè)節(jié)點(diǎn)不夠一組银伟。
給定一個(gè)單鏈表的頭指針head,同時(shí)給定K值，返回逆序后的鏈表的頭指針绘搞。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class KInverse {
public:
ListNode* inverse(ListNode* head, int k) {
// write code here
int cnt = 1;
ListNode *first = head, *curr = head, *next_gp = head,
*local_curr = head, *pre_end = head, *local_pre=head, *local_nxt = head;
while(curr){
if(k == cnt){
// 記錄第一段需要反轉(zhuǎn)的段前和段后
head = curr;
next_gp = curr->next;
local_pre = next_gp;
// 反轉(zhuǎn)內(nèi)部節(jié)點(diǎn)
while(local_curr != next_gp){
local_nxt = local_curr->next;
local_curr->next = local_pre;
local_pre = local_curr;
local_curr = local_nxt;
}
// 為下次做準(zhǔn)備
curr = first;
first = next_gp;
pre_end = curr;
}else if(cnt > k && 0 == cnt%k){
// 記錄段前和段后彤避，并將收尾相連
pre_end->next = curr;
next_gp = curr->next;
local_pre = next_gp;
local_curr = first;
// 反轉(zhuǎn)內(nèi)部節(jié)點(diǎn)
while(local_curr != next_gp){
local_nxt = local_curr->next;
local_curr->next = local_pre;
local_pre = local_curr;
local_curr = local_nxt;
}
// 為下次做準(zhǔn)備
curr = first;
first = next_gp;
pre_end = curr;
}
curr = curr->next;
++cnt;
}
return head;
}
};
