題目
給出一個(gè)鏈表炮障，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)目派，并返回翻轉(zhuǎn)后的鏈表。
k 是一個(gè)正整數(shù)胁赢，它的值小于或等于鏈表的長(zhǎng)度企蹭。如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么將最后剩余節(jié)點(diǎn)保持原有順序智末。
示例 :
給定這個(gè)鏈表：1->2->3->4->5
當(dāng) k = 2 時(shí)谅摄，應(yīng)當(dāng)返回: 2->1->4->3->5
當(dāng) k = 3 時(shí)，應(yīng)當(dāng)返回: 3->2->1->4->5
說明 :
你的算法只能使用常數(shù)的額外空間系馆。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值送漠，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。
思路
題目的難度在于翻轉(zhuǎn)的長(zhǎng)度不再是整個(gè)鏈表的長(zhǎng)度了由蘑。在確定反轉(zhuǎn)長(zhǎng)度的情況下仍然可以利用鏈表的reverse闽寡，用1-2-3-4-5為例，首先反轉(zhuǎn)兩個(gè)變成2-1-3-4-5尼酿，下一次應(yīng)該反轉(zhuǎn)3和4爷狈，利用reverse仍然可以實(shí)現(xiàn)，但要注意的是裳擎，反轉(zhuǎn)后的順序4-3涎永，其中的4必須與前面1聯(lián)系，而3必須與后面的3聯(lián)系，否則整個(gè)鏈表就斷了土辩。另外支救，最后只剩下一個(gè)5時(shí)抢野，其長(zhǎng)度已經(jīng)小于要求的長(zhǎng)度2了拷淘，這時(shí)候應(yīng)該返回NULL，代表與前面的關(guān)系不改變指孤。
首先給出改進(jìn)的reverse函數(shù)启涯，其中head表示當(dāng)前要反轉(zhuǎn)的鏈表段的起始位置，n-1表示還剩有多少個(gè)數(shù)沒有完成反轉(zhuǎn)恃轩，tail表示這段要反轉(zhuǎn)鏈表反轉(zhuǎn)后的尾部（其實(shí)就是反轉(zhuǎn)前此段鏈表的頭部）结洼，begin表示此段鏈表的前一個(gè)結(jié)點(diǎn)，在完成反轉(zhuǎn)后必須與前一個(gè)結(jié)點(diǎn)保持聯(lián)系叉跛。
ListNode* reverse (ListNode* head, int n, ListNode* tail , ListNode* begin)
{
if (head && !head->next && n > 1) return NULL;
if (n == 1)
{
if (head && tail)
{
tail->next = head->next;
}
if (begin)
{
begin->next = head;
}
}
else if (head && head->next && n > 1)
{
ListNode* temp = reverse(head->next, n - 1, tail, begin);
if (temp)
{
temp->next = head;
}
if (!temp)
{
return NULL;
}
}
return head;
}
下面給出調(diào)用reverse的代碼松忍，首先應(yīng)該獲得第一段反轉(zhuǎn)，如果反轉(zhuǎn)的結(jié)果是NULL筷厘，說明整個(gè)鏈表的長(zhǎng)度都不夠鸣峭，則直接返回原鏈表即可。否則的話酥艳，就找到新鏈表開始的位置摊溶，保存下來，作為最后返回時(shí)用充石。完成第一段反轉(zhuǎn)后莫换，下一段反轉(zhuǎn)的起始應(yīng)為第一段的末尾的下一個(gè)結(jié)點(diǎn)，然后繼續(xù)reverse就ok了骤铃。
ListNode* reverseKGroup2(ListNode* head, int k)
{
ListNode* result = head;
int t = k;
while (t > 1 && result)
{
result = result->next;
t--;
}
ListNode* temp = reverse(head, k, head, NULL);
if (!temp) return head;
while (temp && temp->next)
{
temp = reverse(temp->next, k, temp->next, temp);
}
return result;
}
