Q. Reverse the group of k nodes in a link list

INPUT:  1->2>3->4->5->6->7->8     K=2

Then

OUTPUT:  1->0->3->2->5->4->7->6->8

METHOD  1

In  this  method we  are  maintaining  an  array  of  size  k  and  then  putting  first  value  at  index  k  and  second  at  k-1  and  so  on........

Then  we  are  putting  value  back  at  link  list..

Here  is  the  working  code  of  it  using  array.

http://ideone.com/pfo26l

Time  Complexity=  O(n)
Space  Complexity=O(k)

METHOD  2

 It  is  a  really  tricky  method  for  coding.  It  is  asked  to  code  many  times  in  interviews.  But  neglecting  this  question  is  not  a  good  option .One  must  practice  this  one  before.

Inplace  method  of  doing  this  question  and  link - link  swap  for  reversing..

http://ideone.com/oLMHyQ

Let  us  see  the  main  code  of  this.....

node* reverse(node* start,int k)
{

node *curr=start,*prev,*next,*end;
int i=0;
prev=end;
end=start;
if(curr==NULL)
return NULL;

while(i<k &&  curr!=NULL)

{
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
i++;
}
end->next=reverse(curr,k);
return prev;
}

Forming sum tree of a givn tree (nodes are to be replaced with the sum of values of their children)

INPUT:-

OUTPUT:-

Good  question  to  pratice  recursion  and  asked  in  many  interviews  to  check  the  concepts  of  recursion  and  trees.  

Here  is  a  C++  code  for  this

#include<iostream.h>

using namespace std;

struct node

{

    int info;

    struct node* left;

    struct node* right;

};

node* newNode(int data)

{

    struct node* temp = new node;

    temp->info = data;

    temp->left = NULL;

    temp->right = NULL;

  return (temp);

}

int sumTree(node* root)

{

if(root==NULL)

return 0;

int sum=root->info;

root->info=sumTree(root->left) + sumTree(root->right);

return root->info+sum;

}

void preorder(node* root)

{

if(root==NULL)

return;

cout<<root->info<<"        ";

preorder(root->left);

preorder(root->right);

}

int main()

{

struct node *n1 = newNode(1);

    n1->left        = newNode(2);

    n1->right       = newNode(3);

    n1->left->left  = newNode(4);

    n1->left->right = newNode(5);

    n1->right->left  = newNode(6);

    n1->left->right->left = newNode(7);

    n1->left->right->right = newNode(8);

    preorder(n1);

    cout<<endl;

    sumTree(n1);

    preorder(n1);

    

return 0;

}