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.

_k_is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of_k_then left-out nodes in the end should remain as it is.

Example:

Given this linked list:1->2->3->4->5

Fork= 2, you should return:2->1->4->3->5

Fork= 3, you should return:3->2->1->4->5

Note:

• Only constant extra memory is allowed.
• You may not alter the values in the list's nodes, only nodes itself may be changed.

M1 Recursive:

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr) return head;
        int count = 0;
        ListNode* cur = head;
        while (cur != nullptr && count < k) {
            cur = cur->next;
            count++;
        }

        if (count == k) {
            cur = reverseKGroup(cur, k);
            // reverse k sublist
            while (count-- > 0) {
                ListNode *tmp = head->next;
                head->next = cur;
                cur = head;
                head = tmp;
            }
            head = cur;
        }
        return head;
    }
};

M2: Stack

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr) return head;

        stack<ListNode *> st;
        ListNode dummy(-1);
        dummy.next = head;
        ListNode *cur = &dummy;
        ListNode *ad = cur->next;

        while (ad != nullptr) {
            for (int i = 0; i < k && ad != nullptr; ++i) {
                st.push(ad);
                ad = ad->next;
            }
            if (st.size() != k) {
                return dummy.next;
            }
            while (!st.empty()) {
                //ListNode *tmp = st.top();
                cur->next = st.top();
                st.pop();
                cur = cur->next;
            }
            cur->next = ad;
        }
        return dummy.next;
    }
};