给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

Solution

参考：《算法小抄》3.11

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if not head: return None
        b = head
        a = b
        for i in range(k):
            if not b: return head
            b = b.next
        
        def reverse(a, b):
            pre = ListNode()
            cur = a
            nex = a
            while cur != b:
                nex = cur.next
                cur.next = pre
                pre = cur
                cur = nex
            return pre
        
        newHead = reverse(a, b)
        a.next = self.reverseKGroup(b, k)
        return newHead
# @lc code=end

cpp

// @lc code=start
/**
 * 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(!head) return head;
        ListNode* p1 = head;
        ListNode* p2 = p1;
        for(int i=0; i<k; ++i){
            if(!p2) return head;
            p2 = p2->next;
        }

        ListNode* newHead = reverse(p1, p2);
        p1->next = reverseKGroup(p2, k);
        return newHead;
    }
private:
    ListNode* reverse(ListNode* p1, ListNode* p2){
        ListNode* pre = new ListNode();
        ListNode* cur=p1, *nex=p1;
        while(cur != p2){
            nex = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        return pre;
    }
};
// @lc code=end

• 非递归实现，参考 liuyubobobo

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummyHead = new ListNode(-1);
        dummyHead->next = head;
        ListNode* pre = dummyHead;
        
        while(pre && pre->next){

            ListNode* end = pre;
            int i;
            for(i = 0; i < k && end->next; i ++)
                end = end->next;

            if(i != k) break;

            ListNode* next = end->next;

            // reverse from pre->next to end
            ListNode* rhead = reverse(pre->next, end);

            ListNode* tail = pre->next;
            pre->next = rhead;
            tail->next = next;
            pre = tail;
        }

        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }

private:
    ListNode* reverse(ListNode* head, ListNode* end){
        if(head == end) return head;
        ListNode* rhead = reverse(head->next, end);
        head->next->next = head;
        return rhead;
    }
};