題目描述
這道題是leetcode的第25題，下面是題目的描述。
給你一個連結串列，每 k 個節點一組進行翻轉，請你返回翻轉後的連結串列。
k 是一個正整數，它的值小於或等於連結串列的長度。
如果節點總數不是 k 的整數倍，那麼請將最後剩餘的節點保持原有順序。
進階：
你可以設計一個只使用常數額外空間的演算法來解決此問題嗎？
你不能只是單純地改變節點內部的值，而是需要實際進行節點交換。
連結：https：//leetcode-cn。com/problems/reverse-nodes-in-k-group
著作權歸領釦網路所有。商業轉載請聯絡官方授權，非商業轉載請註明出處。
非遞迴解法分析
題意就是要把一個單鏈表做翻轉，但是會給一個K作為翻轉的單位。下圖是一個例子，其中K=2，原連結串列是［1，2，3，4，5］，在翻轉過後是［2，1，4，3，5］。
K=2
觀察連結串列，我們可以把連結串列分成［1，2］，［3，4］，［5］，其中最後一個長度小於K，所以不需要翻轉，只需要翻轉前面兩個長度為K的子連結串列。翻轉連結串列是一個常規操作，我們只要知道了開始節點的前一個節點，以及末尾節點的後一個節點，就可以對這個子連結串列做翻轉操作了。
實現程式碼及分析
以上思路的實現程式碼如下，這個解法不需要遞迴，時間複雜度是O（N），空間複雜度是O（1）。
/** * Definition for singly-linked list。 * struct ListNode { * int val； * ListNode *next； * ListNode（） ： val（0）， next（nullptr） {} * ListNode（int x） ： val（x）， next（nullptr） {} * ListNode（int x， ListNode *next） ： val（x）， next（next） {} * }； */class Solution {public： ListNode* reverseKGroup（ListNode* head， int k） { if（k == 1） { return head； } if（！head） { return head； } ListNode* v_head = new ListNode（0， head）； ListNode* p = v_head； ListNode* q = v_head； int cursor = 0； while（q->next） { cursor++； q = q->next； if（cursor % k == 0） { ListNode* pre = p； ListNode* pos = q->next； p = pre->next； q = p； reverseList（pre， pos）； } } return v_head->next； } void reverseList（ListNode* pre， ListNode* pos） { ListNode* p = pre->next； ListNode* q = pos； while（p ！= pos） { ListNode* next = p->next； p->next = q； q = p； p = next； } pre->next = q； }}；
因為在網路上已經有許多遞迴解決這個問題的文章，所以我就不再分析遞迴的思路了，讀者如果感興趣的話可以自己搜尋一下。
