Reverse every Nth node in LL

/* Problem Statement :
 * Given a Linked List, reverse every Nth node in the Linked List
 */
#include<iostream.h>

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

NODE *form_LL(int limit)
{
    NODE *head = NULL;
    for(int i = limit;i ; --i)
    {
        NODE *temp = new NODE;
        temp->data = i;
        temp->next = head;
        head = temp;
    }
    return head;
}
void print_LL(NODE *start)
{
    while(start)
    {
        cout<<start->data<<" ";
        start = start->next;
    }
    cout<<endl;
}
NODE *KReverse(NODE *head, int k)
{
    int count = 0;

    if(!head)
        return NULL;
    NODE *prev = NULL;
    NODE *current = head;
    NODE *next = NULL;
    while(current && count < k)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
        count++;
    }
    NODE *rest = KReverse(next, k);
    head->next = rest;
    return prev;
}

int main()
{
    int num;
    cout<<"How many number of Nodes : ";
    cin>>num;
    NODE *head = form_LL(num);
    print_LL(head);

    int k = 0;
    cout<<"How many rotations : ";
    cin>>k;
    NODE *new_node = KReverse(head, k);
    print_LL(new_node);
}

Advertisement

~ by Ganesh on December 31, 2008.