Linked List Related

Brief list of simple problems based on linked list and their solutions.
Most of them are recursive approaches and they can be written iteratively also.

1.Given a linked-list and 2 integers k & m. Reverse the linked-list till k elements and then traverse till m elements and repeat.
2.Reverse a Linked List(Recursion and Iterative methods).
3.Print Linked List in Reverse & Alternative nodes.

#include<iostream>
#include<sstream>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;



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


void push(struct node **head_first,int data){
 struct node *new_node=NULL;
 new_node=(struct node*)malloc(sizeof(struct node));
 
 new_node->data=data;
 new_node->next=(*head_first);
 *head_first=new_node;
}

void printAll(struct node *head){
 while(head!=NULL){
  cout<<head->data<<"\t";
  head=head->next;
 }
}

void printInReverse(struct node *head){
 if(head==NULL){
  return;
 }
 printInReverse(head->next);
 cout<<head->data<<"\t";
}

void printAlternative(struct node *head){
 if(head==NULL){
  return;
 }
 cout<<head->data<<"\t";
 if(head->next!=NULL){
  printAlternative(head->next->next);
 }
}

struct node* reverseListRecursion(struct node** head_first,struct node** head){
 
 struct node *curr=(*head_first);
 
 if(curr->next==NULL){
  *head=curr;
  return curr;
 }
 
 struct node **next=NULL;
 next=&(curr->next);
 
 reverseListRecursion(next,head)->next=curr;
 
  
 return curr;
}

struct node* reverseListIteration(struct node* head){
 if(head!=NULL){
  struct node* prevN=NULL;
  struct node* currN=head;
  struct node* nextN=head->next;
  
  while(nextN!=NULL){
   currN->next=prevN;
   prevN=currN;
   currN=nextN;
   nextN=nextN->next;
  }
  currN->next=prevN;
  return currN;
 }
}


struct node* reverseList(struct node** root,struct node** head,struct node** revHead,int i,int k){
    if(root==NULL && i<k){
        return NULL;
    }
    
    if(i==k){
        (*head)=(*root)->next;
 (*revHead)=(*root);
        return *root;
    }
    
    struct node* curr=*root;
    struct node* nextN=reverseList(&(curr->next),head,revHead,i+1,k);
    if(nextN!=NULL){
        nextN->next=curr;
    }else{
        return NULL;
    }
    
    if(i==1 && *head !=NULL){
        curr->next=(*head);
        return *head;
    }
    
    return curr;
}

void reverseAndTraverse(struct node *root, int k,int m){
    struct node *kNode=NULL; // K th Node - Assuming Node count from 0 :P
    struct node *revHead=NULL;

    kNode=reverseList(&root,&kNode,&revHead,1,k);
    
    if(kNode==NULL){
        printf("InSufficient Linked List\n");
        return;
    }
    
    int i=0;
    while(i<m && kNode!=NULL){
        printf("%d ",kNode->data);
        kNode=kNode->next;
 i++;
    }    

 cout<<endl; 

  while(revHead!=NULL){
  printf("%d ",revHead->data);
  revHead=revHead->next;
 }
}



int main(){
 struct node *head=NULL;
 
 push(&head,6);
 push(&head,5);
 push(&head,4);
 push(&head,3);
 push(&head,2);
 push(&head,1);
 
 
 cout<<"Printing In Normal:\t";
 printAll(head);cout<<endl;
 
 cout<<"Printing In Reverse:\t";
 printInReverse(head);cout<<endl;

 cout<<"Printing In Alternative:\t";
 printAlternative(head);cout<<endl;
 
 cout<<"Converting to Reverse:\n";
 struct node* revHead=NULL;
 reverseListRecursion(&head,&revHead)->next=NULL; 
 head=revHead;
 
 cout<<"After the Reversal-1:\t";
 printAll(head);cout<<endl;
 
 cout<<"Converting to Reverse Again:\n";
 head=reverseListIteration(head); 
 
 cout<<"After the Reversal-2:\t";
 printAll(head);cout<<endl;
 
 cout<<"Perform Reverse of K and Traversal of M \t";
 int n=1;
 scanf("%d",&n);
 reverseAndTraverse(head,n,3);cout<<endl;

 
}