25. Reverse Nodes in k-Group

recursive O(n)
这个更清楚

# 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:
        p = head
        for i in range(k):
            if not p:
                return head
            p = p.next
        curr, prev = head, self.reverseKGroup(p, k)
        for i in range(k):
            succ = curr.next
            curr.next = prev
            prev = curr
            curr = succ
        return prev

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto p = head;
        int i = 0;
        for (; i < k && p; ++i) {
            p = p->next;
        }
        if (i < k) return head;
        auto prev = reverseKGroup(p, k), curr = head;
        while (k-- > 0) {
            auto succ = curr->next;
            curr->next = prev;
            prev = curr;
            curr = succ;
        }
        return prev;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto p = head;
        int t = k; // 这里不能用k因为后边还得用
        while (t-- > 0 && p) {
            p = p->next;
        }
        if (t >= 0) return head; // 这里检查尾部较短的部分，必须统计t因为p为nullptr时也可能需要reverse，并且t == 0也是有可能的因为t最后还要--
        auto prev = reverseKGroup(p, k), curr = head; // 一个正常的翻转链表操作
        while (k-- > 0) {
            auto succ = curr->next;
            curr->next = prev;
            prev = curr;
            curr = succ;
        }
        return prev;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto p = head;
        int i = 0;
        for (; i < k && p; ++i, p = p->next);
        if (i < k) return head;
        auto prev = reverseKGroup(p, k), curr = head;
        for (int i = 0; i < k; ++i) {
            auto succ = curr->next;
            curr->next = prev;
            prev = curr;
            curr = succ;
        }
        return prev;
    }
};