Reverse a Linked List in groups of given size

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

Example:
Inputs:  1->2->3->4->5->6->7->8->NULL and k = 3 
Output:  3->2->1->6->5->4->8->7->NULL. 

Inputs:   1->2->3->4->5->6->7->8->NULL and k = 5
Output:  5->4->3->2->1->8->7->6->NULL. 

struct Node *reverse (struct Node *head, int k)

{

    struct Node* current = head;

    struct Node* next = NULL;

    struct Node* prev = NULL;

    int count = 0;  

     

    /*reverse first k nodes of the linked list */

    while (current != NULL && count < k)

    {

        next  = current->next;

        current->next = prev;

        prev = current;

        current = next;

        count++;

    }

     

    /* next is now a pointer to (k+1)th node

       Recursively call for the list starting from current.

       And make rest of the list as next of first node */

    if (next !=  NULL)

       head->next = reverse(next, k);

    /* prev is new head of the input list */

    return prev;

}

In this post, we have used a stack which will store the nodes of the given linked list. Firstly, push the k elements of the linked list in the stack. Now pop elements one by one and keep track of the previously popped node. Point the next pointer of prev node to top element of stack. Repeat this process, until NULL is reached.

This algorithm uses O(k) extra space.

struct Node* Reverse(struct Node* head, int k)

{

    // Create a stack of Node*

    stack<Node*> mystack;

    struct Node* current = head;

    struct Node* prev = NULL;

 

    while (current != NULL) {

 

        // Terminate the loop whichever comes first

        // either current == NULL or count >= k

        int count = 0;

        while (current != NULL && count < k) {

            mystack.push(current);

            current = current->next;

            count++;

        }

 

        // Now pop the elements of stack one by one

        while (mystack.size() > 0) {

 

            // If final list has not been started yet.

            if (prev == NULL) {

                prev = mystack.top();

                head = prev;

                mystack.pop();

            } else {

                prev->next = mystack.top();

                prev = prev->next;

                mystack.pop();

            }

        }

    }

 

    // Next of last element will point to NULL.

    prev->next = NULL;

 

    return head;

}