Leetcode 25: reverse nodes in k group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

这个题目是在swap nodes in pair的基础上的拓展题。 其实解法跟swap nodes in pair相似，只不过这里需要注意： 1. base case 情况的处理，当iterate链表发现长度> n 并且cur 为空的时候就直接返回head， 2. 对于head sample的处理不能像之前那样简单了，而是需要用到K个nodes的reverseLinklist的操作。所以这个题目的解法是结合： swap nodes in pair 和 reverselinklist的结合。  

class Solution {
private:
    ListNode* reverse(ListNode* head) {
        //sanity check
        if (head == NULL || head->next == NULL) return head;
        ListNode* cur = head;
        ListNode* pre = NULL;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        //sanity check
        if (head == NULL) return head;
        //base case
        int count = 0;
        ListNode* p = head;
        while(p) {
             count++;
            if (count == k) break;
            p = p->next;
            if (count < k && (p == NULL)) return head;
        }
        ListNode* next  = p->next;
        ListNode* newhead = reverseKGroup(next, k);
        p->next = NULL;
        ListNode* bp = reverse(head);
        head->next = newhead;
        return bp;
    }
};
time complexity: O(2*n)每个节点走两边
space complexity: O(k)

M2: iterative 的方法
 这题的iterative的方法和swap nodes in list的方法相似，由于head节点会发生改变，所以需要dummy node来简化corner case， 为了进行指针变换，需要3个辅助节点，pre, cur, nnext， 对于中间的k个需要reverse的节点不需要进行记录，只需要知道reverse之后的头结点和尾节点。 这也是swap nodes in pair中对指针变换的思想。
class Solution {
private:
    ListNode* reverse(ListNode* head) {
        //sanity check
        if (head == NULL || head->next == NULL) return head;
        ListNode* cur = head;
        ListNode* pre = NULL;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        //sanity check
        if (head == NULL) return head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* cur = head;
        ListNode* pre = dummy;
        int count = 0;
        ListNode* tail = cur;
        while(tail) {
            count++;
            ListNode* nnext = tail->next;
            if (count == k) {
                tail->next = NULL;
                ListNode* nnode = reverse(cur);
                pre->next = nnode;
                cur->next = nnext;
                pre = cur;
                cur = nnext;
                count = 0;
            }else if (count < k && tail == NULL) break;
            tail = nnext;
        }
        return dummy->next;
    }
};