ronith
7/9/2018 - 8:57 AM

Reverse a Linked List in groups of given size | Set 1

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.

Algorithm: reverse(head, k)

  1. Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev.
  2. head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
  3. return prev /* prev becomes the new head of the list
Reverse a Linked List in groups of given size Set 1.cpp
content_copyfile_download
// https://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/
#include <bits/stdc++.h>
using namespace std;

struct linked_list {
    int data;
    struct linked_list *next;
};
typedef struct linked_list node;

void print (node* n) {
    while (n) {
        cout<< n->data<< "->";
        n = n->next;
    }
    cout<< "NULL";
    return;
}

node* insert(node* head, int n) {
    node* temp = new node;
    temp->data = n;
    if (head == NULL) {
        temp->next = head;
        head= temp;
        return head;
    }
    temp->next = NULL;
    node* last = head;
    while (last->next)
        last = last->next;
    last->next = temp;
    return head;
}

node* ReverseList (node* head, int k) {
    node *prev = NULL, *current = head, *next = NULL;
    int c = 0;
    while (current && c<k) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
        c++;
    }
    if (current!=NULL)
        head->next = ReverseList(current,k);
    return(prev);
}

int main() {
    int n,k;
    node* head=NULL;
    while (true) {
        cout<< "Enter the number: ";
        cin>>n;
        if (n==-9)
            break;
        else
            head = insert(head, n);
    }
    print(head);
    cout<< "Enter the set size: ";
    cin>> k;
    head = ReverseList(head,k);
    print(head);
}