Reversing Link List in group of n nodes without using any other data type in O(n) time

Some ways of reversing a link list using other data types are-
1.Use the stack. We can push all the elements on to the stack and then poop out each element. 
2.Similarly, we can also create a new link list. Starting from the head of the current list, we can create  new list by adding nodes in the front of the new list.

A link list can be reversed without using any other data type by using three pointers as shown in the code below.

//created by Aditya Vijayvergia

//uploaded on thecodingedge.blogspot.com

#include<stdio.h>

#include<conio.h>

struct node

{

  int data;

  struct node* next;

}*head;

typedef struct node node;

node* rev(int n)

{

  node *p,*q,*r,*t2,*t1;

  int c=0,start=1;

  t2=head;

  t1=NULL;

  p=head;

  q=head->next;

  r=q->next;

  while(q!=NULL)

  {

    //printf("c<n-1\n\t%d",p->data);

    //getch();

    if(c==n-1)

    {

      //printf("c=n-1");

      //getch();

      c=0;

      if(t1!=NULL)

    t1->next=p;

      t1=t2;

      t2=q;

      if(start==1)

      {

    start=0;

    head=p;

      }

      p=q;

      q=p->next;

      r=q->next;

    }

    q->next=p;

    p=q;

    q=r;

    r=r->next;

    c++;

  }

  t1->next=p;

  t2->next=NULL;

  return head;

}

void main()

{

  node *q;

  node* p;

  int i;

  clrscr();

  head=(node*)malloc(sizeof(node));

  p=head;

  //q->next=NULL;

  head->data=1;

  //p->next=NULL;

  for(i=2;i<15;i++)

  {

    q=(node*)malloc(sizeof(node));

    q->next=NULL;

    q->data=i;

    p->next=q;

    p=p->next;

  }

  p=head;

  printf("Initial link list is:\n");

  while(p!=NULL)

  {

    printf("%d->",p->data);

    p=p->next;

  }

  printf("\n\n\n\nUsing n=3\n");

  head=rev(6);

  p=head;

  printf("\n\n\nReversed link list is:\n");

  while(p!=NULL)

  {

    printf("%d->",p->data);

    p=p->next;

  }

  getch();

}

The output of the program is given below.

Converting Postfix Expression to Prefix Expression and Infix Expression in C

In prefix expression, the operator comes before the operands where as in postfix expression, the operator comes in the end. So to convert a postix expression to a prefix expression, we just have to 

bring the operator in the front for each sub expression.

For doing this we use a stack that stores a 2D character array. We can visualize it like a 1D character array that stores operands. The push operation pushes an operand to the stack and the pop operation returns a pointer to the last operand.

First push the operands on to the stack until an operator is encountered. When an operator is encountered we pop the last two operands and create a new character array.

 Now if we want to convert to infix expression then we store the first operand then the operator and then the second operand. Similarly for prefix expression we first store the operator and then the two operands in order.We then push this newly created character array to the stack.

The logic is that the character array that we pushed will now act as an operand for further operations.

The source code for prefix expression is given below.

//created by Aditya Vijayvergia
//uploaded on thecodingedge.blogspot.com
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#define size 20
struct stack
{
  char data[size][size];
  int top;
}s;
void push(char x[20])
{
  int i;
  s.top++;
  for(i=0;i<strlen(x);i++)
   s.data[s.top][i]=x[i];
}
char* pop()
{
char *p;
if(s.top==-1)
  return NULL;
return s.data[s.top--];
}

void main()
{
  char q[50],c[50];
  char *a,*b;
  int i,j,a1,b1;
  s.top=-1;
  clrscr();
  printf("\nenter postfix expression:");
  gets(q);
  for(j=0;j<strlen(q);j++)
  {
  if(q[j]>='a'&&q[j]<='z')
    {
    s.data[++s.top][0]=q[j];
    //printf("\npush %c",q[j]);
    }
  else
  {
  b=pop();
  a=pop();
  //printf("\na=%s\tb=%s",a,b);
  c[0]=q[j];
  a1=strlen(a);
  b1=strlen(b);
  for(i=0;i<a1;i++)
    {
    c[i+1]=*a;
    a++;
    }
  for(i=0;i<b1;i++)
    {
    c[a1+i+1]=*b;
    b++;
    }
  push(c);
  //printf("\npushed operand %s",c);
  }
  a=NULL;
  b=NULL;
  }
  printf("\n\nPrefix expression : %s",pop());
  getch();
}