We are given a pointer to the head of a singly Linked List and you have to write a function to reverse the elements of the given singly Linked List in alternate groups of K nodes. Once the operation is performed, pointer to the head of the Linked List must be returned from the function.

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 
and 
k = 3

Output: 3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 9 -> 8 -> 7 -> 10

In the above example, k is equal to 3. Therefore we are required to reverse the elements of the linked list in alternate groups of 3 i.e. we reverse first 3 elements 1 → 2 → 3 to 3 → 2 → 1, then keep next 3 elements in same order i.e. 4 → 5 → 6 and repeat this process for remaining nodes. As a result of the above operation we obtain the linked list having elements 3 → 2 → 1 → 4 → 5 → 6 → 9 → 8 → 7 → 10 and in that order.

We have explored two approaches:

• Recursive implementation
• Iterative implementation

Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

Approach 1: Recursive Implementation

Algorithm

Step 1: Reverse first K elements in the Linked List. While doing that let curr be current node, prev be previous node of curr and next be node pointed by curr->next.
Step 2: Skip reversing next K nodes.
Step 3: Now, recursively call reverseKGroupAltRecursive(curr.next, k) where curr.next points to the (2K+1)-th node and the pointer to resultant list returned by the function is stored in curr->next where curr currently points to 2K-th node.
Step 3: Return prev as it now points to the head of resultant list.

Pseudocode

reverseKGroupAltRecursive(head, k)
    curr = head
    prev = nullptr
    next = nullptr
    
    count = 0
    WHILE count < k AND curr 
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
        count = count + 1
    
    IF head
        head.next = curr
        
    count = 0
    WHILE count < k-1 AND curr
        curr = curr.next
        count = count + 1
        
    IF curr
        curr.next = reverseKGroupAltRecursive(curr.next, k)

    return prev

Implementation

Following is the C++ implementation:

#include <iostream>

using namespace std;

struct Node {
    int val;
    struct Node *next;
    Node(int x): val(x), next(nullptr) {}
};

Node* reverseKGroupAltRecursive(Node *head, int k) {

    struct Node *curr = head;
    struct Node *prev = nullptr;
    struct Node *next = nullptr;

    // Reverse nodes in groups of k
    int count = 0;
    while(count < k && curr != nullptr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
        count++;
    }

    // Make K-th node (head) point to K+1-th node (curr)
    if(head != nullptr)
        head->next = curr;

    // skip next K-1 nodes
    count = 0;
    while(count < k-1 && curr != nullptr) {
        curr = curr->next;
        count++;
    }

    // Check if the end of linked list is reached
    // If not, then make a recursive call to alternatively reverse remaining nodes
    if(curr != nullptr)
        curr->next = reverseKGroupAltRecursive(curr->next, k);

    return prev;
}

int main() {
    
    // Creating singly linked list
    // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 
    struct Node *head = new Node(1);
    struct Node *curr = head;
    for(int i=2;i<=8;i++) {
        curr->next = new Node(i);
        curr = curr->next;
    }

	// Initialize k
	int k = 3;
	
	// Reverse first K nodes of linked list
    head = reverseKGroupAltRecursive(head, k);

	// Print list elements
    while(head) {
        cout<<head->val<<" ";
        head = head->next;
    }
    cout<<endl;

    return 0;
}

Explanation

• Consider singly linked list where Node pointer head points to first node in 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 and let k = 3.
• Three Node pointers curr, prev and next are created having values of head, NULL and NULL.
• Now, we try to reverse the first K nodes i.e. 3 nodes of the linked list inside the while loop. We loop through the list as long as count value is less than k and curr is not NULL.
• During each iteration each node is reversed and prev points to the reversed linked list i.e. after first iteration prev points to 1 and next points to 2 → 3 → 4 → 5 → 6 → 7 → 8 , after second iteration prev points to 2 → 1 and next points to 3 → 4 → 5 → 6 → 7 → 8 and after third iteration prev points to 3 → 2 → 1 and next points to 4 → 5 → 6 → 7 → 8 after which the loop breaks as count is equal to k.
• head points to the K-th node in reversed linked list i.e. head points to 1 in 3 → 2 → 1 as it's pointer value remains unchanged.
• If head is not NULL, make head.next point to curr where curr points to the remaining nodes to be processed in the linked list. This operation joins the tail of reversed linked list to the head of remaining linked list to be processed.
• Now we skip the next K nodes using a while loop as we are reversing the linked list in alternative groups of K. We skip until 2K-th node is reached and exit the loop. curr points to 2K-th node. The linked list we have processed so far is 3 → 2 → 1 → 4 → 5 → 6 and curr points to node with value 6. Still 7 → 8 are yet to be processed.
• If curr is not NULL, we make a recursive call to reverseKGroupAltRecursive function to alternatively reverse nodes from (2K+1)-th positon which is pointed by the pointer curr.next and the above process repeats. The pointer to the alternatively reversed linked list returned from the recursive call is saved to curr->next where curr points to the 2K-th node in list pointed by prev.
• Therefore, prev now points to the final list 3 → 2 → 1 → 4 → 5 → 6 → 8 → 7
• Finally prev pointer is returned.

Approach 2: Iterative Implementation

Algorithm

Step 1: Reverse first k nodes of the linked list.
Step 2: While reversing, we keep track of the first and last node of the reversed linked list using the join and tail pointer.
Step 3: After reversing the k nodes of the linked list, we join the nodes pointed by the tail pointer and join pointer and make tail point to last node of the reversed resultant linked list.
Step 4: Skip reversing the next K nodes as the linked list needs to be alternatively reversed.
Step 4: We repeat this process until all groups of nodes are alternatively reversed.

Pseudocode

reverseKGroupAltIterative(head, k)
    curr = head
    prev = nullptr
    tail = nullptr
    finalHead = nullptr
    
    WHILE curr
        join = curr
        prev = nullptr 
        count = 0
        
        WHILE count < k and curr 
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
            count = count + 1
        
        IF NOT finalHead
            finalHead = prev
        IF tail
            tail.next = prev
        
        tail = join
        tail.next = curr
        
        count = 0
        WHILE count < k AND curr
            prev = curr
            curr = curr.next
            count = count + 1
        tail = prev
    
    return finalHead

Implementation

Following is the C++ implementation:

#include <iostream>

using namespace std;

struct Node {
    int val;
    struct Node *next;
    Node(int x): val(x), next(nullptr) {}
};

Node* reverseKGroupAltIterative(Node *head,int k) {
    Node *curr = head;
    Node *prev = nullptr;
    Node *tail = nullptr;
    Node *finalHead = nullptr;

    while(curr != nullptr) {
        // join points to first node in group of k node
        // On reversal join points to the last node as order is changed
        Node *join = curr;
        
        // Reset the value of prev
        prev = nullptr;

        int count = 0;
        while(count < k && curr != nullptr) {
            Node *next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
            count++;
        }

        // finalHead points to main resultant list
        if(finalHead == nullptr)
            finalHead = prev;

        // Join main resultant list and the reversed list 
        if(tail != nullptr)
            tail->next = prev;
        
        // Pointing tail pointer to the new tail node
        tail = join;
        // Joining the remaining list to be processed with the resultant list
        tail->next = curr;
        
        // Next task is to skip next K nodes
        count = 0;
        while(count < k && curr != nullptr) {
            prev = curr;
            curr = curr->next;
            count++;
        }
        // Make tail pointer point to the new tail node after skipping K nodes
        tail = prev;
    }
    return finalHead;
}

int main() {
    
    // Creating singly linked list
    // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
    struct Node *head = new Node(1);
    struct Node *curr = head;
    for(int i=2;i<=8;i++) {
        curr->next = new Node(i);
        curr = curr->next;
    }

	// Initialize k
	int k = 3;
	
	// Reverse first K nodes of linked list
    head = reverseKGroupAltIterative(head, k);

	// Print list elements
    while(head) {
        cout<<head->val<<" ";
        head = head->next;
    }
    cout<<endl;

    return 0;
}

Explanation

• Consider singly linked list where Node pointer head points to first node in 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 and let k = 3.
• Four Node pointers curr, prev, tail and finalHead are created having values of head, NULL, NULL and NULL.
• During, each iteration of outer loop, we set the value of join and prev to curr and NULL respectively.
• Now, we reverse the first K nodes i.e. 3 nodes of the linked list. We loop through the list as long as count value is less than k and curr is not NULL.
• During each iteration of inner loop, each node is reversed and prev points to the reversed linked list i.e. after first iteration prev points to 1 and curr points to 2 → 3 → 4 → 5 → 6 → 7 → 8 , after second iteration prev points to 2 → 1 and curr points to 3 → 4 → 5 → 6 → 7 → 8 and after third iteration prev points to 3 → 2 → 1 and curr points to 4 → 5 → 6 → 7 → 8 after which the loop breaks as count is equal to k.
• finalHead pointer is used to point to resultant final reversed linked list. For that, during the first iteration of outer loop we point finalHead to the reversed list we get 3 → 2 → 1. In the successive iterations, we simply append the reversed list obtained at the end of list pointed by finalHead i.e. after second iteration of outer loop finalHead points to 3 → 2 → 1 → 4 → 5 → 6 and in the last outer loop iteration finalHead points to 3 → 2 → 1 → 4 → 5 → 6 → 8 → 7.
• Next, if the tail is not NULL, we are setting tail.next's value equal to prev and this basically appends the reversed linked list to the reversed resultant linked list pointed by finalHead.
• Next step is to update value tail pointer by setting it to join pointer value which makes tail now point to last node present in resultant linked list. tail.next is set to the value of curr where curr points to the remaining nodes of the linked list to be reversed.
• Now we have to skip next K nodes and this is done by using a while loop and we store the previous node in each step using prev. When curr points to (2K+1)-th node, we breakout of the loop. Now tail pointer's value is set to prev where prev points to 2K-th node. This becomes the new tail node.
• In the end, finalHead points to the final linked list 3 → 2 → 1 → 4 → 5 → 6 → 8 → 7.
• finalHead pointer is returned from the function.

With this article at OpenGenus, you must have the complete idea of algorithm to reverse alternate groups of K nodes in a Singly Linked List. Enjoy.