題目
給你一個(gè)鏈表，每k個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)猿规，請(qǐng)你返回翻轉(zhuǎn)后的鏈表衷快。
k是一個(gè)正整數(shù)，它的值小于或等于鏈表的長(zhǎng)度姨俩。
如果節(jié)點(diǎn)總數(shù)不是k的整數(shù)倍蘸拔，那么請(qǐng)將最后剩余的節(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)交換邓萨。
題目分析
基本的思路就是根據(jù)k來逐步翻轉(zhuǎn)鏈表地梨。
為了方便操作，給原始鏈表添加頭結(jié)點(diǎn)缔恳，然后遍歷一次鏈表湿刽，獲得鏈表長(zhǎng)度，利用鏈表長(zhǎng)度計(jì)算迭代次數(shù)褐耳。
int len = 0;
while (head){
len++;
head = head->next;
}
int it = len / k;
然后需要實(shí)現(xiàn)鏈表部分翻轉(zhuǎn)诈闺，假設(shè)這個(gè)鏈表的起始結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)是pre，首結(jié)點(diǎn)為cur铃芦，需翻轉(zhuǎn)k個(gè)元素：
for (int i = 1; i < k; i++){
list next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
pre = cur;
cur = pre->next;
找一組數(shù)字來驗(yàn)證上述過程雅镊，鏈表0->1->2->3->4->5，我們需要翻轉(zhuǎn)1 2 3刃滓，pre = 0, cur = 1:
- 第一步仁烹，
next = 2, cur->next = 3(1->3),next->next = 1(2->1),pre->next = 2(0->2),局部鏈表變?yōu)椋?code>0->2->1->3 - 第二步，
next = 3, cur->next = 4(1->4),next->next = 2(3->2),pre->next = 3(0->3),局部鏈表變?yōu)椋?code>0->3->2->1 - 局部變換完成咧虎。
題目解答
typedef struct ListNode* list;
struct ListNode* reverseKGroup(struct ListNode* head, int k){
list dummy = (list)malloc(sizeof(struct ListNode));
dummy->next = head;
list pre = dummy;
list cur = pre->next;
int len = 0;
while (head){
head = head->next;
len++;
}
int it = len / k;
while (it--){
for (int i = 1; i < k; i++){
list next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
pre = cur;
cur = pre->next;
}
return dummy->next;
}
