Skip to main content

Program to Swap Adjecent nodes in single linked list

shiv@ubuntu:~/ds/list$ cat   altxchangenode.c
/*
 * program to Xchange or swap all the adjecent nodes(not node data) in the single linked list
 */

#include<stdio.h>
#include<stdlib.h>
#define MAX 10
struct list
{
 int d;
 struct list *next;
};
/*
 * function to swap 2 adjecent nodes(linkes) in the list
 */
void xchangenodes(struct list **head, struct list **ne, struct list **tm)
{
  struct list *temp, *x1, *x2;

  if(*tm == NULL){
     return;
  }

  if((*tm)->next && (*tm)->next->next){
      /*next node when more than 3 nodes present in the list */
     temp=(*tm)->next->next;
  } else if((*tm)->next){
      if(*head != NULL) {   /* only two nodes present in the list */
         (*ne)->next = (*tm)->next;
         (*ne)->next->next = *tm;
         (*tm)->next = NULL;
      } else {
          /* last iteration where last 2 nodes we need to swap */
         *head=(*ne)->next;
         (*head)->next =*tm;
         (*tm)->next = NULL;
      }
      *tm = NULL;
      return;
  } else {
      if(*head ==NULL){ /*if only one node is present*/
         *head=*tm;
         (*tm)->next = NULL;
      } else {
         (*ne)->next=*tm;  /*only one node left for last iteration */
         (*tm)->next = NULL;
      }
      *tm=NULL; /*terminate loop which calls this function */
      return;
  }

   x1=(*tm);
   x2=(*tm)->next;

   if(*head == NULL){
     /* if more than 3 nodes present in list, adjust head */
      x2->next=x1;
      x1->next = temp;
      *head = x2;
      *tm = temp;
      *ne=x1;
   }

   /* swap nodes and set next node after swap*/
   x2->next = x1;
   x1->next = temp; /*temp hold rest of the list after swaping 2 nodes */
   (*ne)->next = x2; /* next iteration we start from (*ne) ie X1 here */
   *ne = x1;
   *tm= temp; /* ne and temp are not same */

}

/* function to display nodes in the list */
void display(struct list *h)
{
  printf("List elements are \n");
  while(h !=NULL)
  {
    printf("%d\n", h->d);
    h=h->next;
  }
}

/* main function to help  test program */
int main()
{
  struct list *head=NULL, *temp=NULL, *next=NULL;
  /* array to build list and test program */
  int a[MAX]={1,2,3,4,5,6,7,8,9,10};
  int i;

  for(i=0;i<MAX; i++){
      temp=malloc(sizeof(struct list));
      if(!temp){
     printf("Memory allocation failure\n");
     return;
      }
     temp->d = a[i];
     temp->next = NULL;
     /* building list simply by inserting element at begining */
     if(head == NULL){
    head = temp;
     } else {
    temp->next = head;
    head = temp;
    }
 }

 display(head);

  /* Xchange all adjecent nodes */

  temp = next = head;
  head = NULL;
  while(temp != NULL) {
        /* temp is updated in function xchangenodes(), as we can't do
         *  temp=temp->next here
         */
        xchangenodes(&head, &next, &temp);

  }
 display(head);
}
/*end of program */
Labels:

Comments

Post a Comment

Popular posts from this blog

C Program to Simulate Linux Cat command

/*  * C program to Simulate Implementation of  Linux *cat* command  * This program will not handle redirection  * you can try to improve this program to handle redirection of file contents  */ #include<stdio.h> #include<string.h> #define MAX_FILE_NAME_CHARS 255 int main(int argc, char *argv[]) {  FILE *fp;  char file_name[MAX_FILE_NAME_CHARS], ch;  int i;  /*   * after creating a.out, rename it as mycat for our own cat command   * and it usage is same as standard cat command   */  if(argc<1){     printf("Usage mycat <filename> \n");     return 0;  }  /*   * cat handles more than one file   * so we need this loop to handle all the files provided   * on command line   */  for(i=1; i<=argc;i++){     /* no need of copy but for understanding purpose, i have created      * str...
4 comments
Read more

simple program to create Orphan process

shiv@ubuntu:~/ds/unix$ cat  orp.c /*  * Program to create orphan process @ Linux  * getpid() gives process PID and   * getppid() gives process's parent ID   * here main() process ID is parent id is current shells PID  * once process becomes orphan it is adopted by init process(it's PID is 1)  */   #include<stdio.h> #include<unistd.h> int main() {  pid_t p; /* create child process */  p=fork();  if(p==0) {     /* fork() returns Zero to child */     sleep(10);  }  printf("The child process pid is %d parent pid %d\n", getpid(), getppid()); /*parent/child waits for 20 secs and exits*/  sleep(20);  printf("\nProcess %d is done its Parent pid %d...\n", getpid(), getppid());  return 0; } O/p shiv@ubuntu:~/ds/unix$ ./a.out The child process pid is 2575 parent pid 1922 The child process pid is 2576 parent pid 2575 Process 2575 is done it...
3 comments
Read more

C99 and C11 standards

as part of my job  sometimes I get chance to interview C programmers, till today, number of  C programmers I have interviewed none knows about new(C11 & C99) features of C programming language, some even not heard of these standards that made me to add  this page, I strongly believe if we are working on product which is born out of C programming, one needs to know about C99 and C11 features as well as Safe-C libraries which improves software quality and security C99 standard has become absolute by now, considering C11 standard which is part of our products which are written in C programming language.  if we name few missing elements in C89 programming features 1) No array bounds checking 2) No variable length arrays 3) No inline functions 4) No support for Boolean data type 5) No complex number type support 6) No single line comment (//) 7) No variable number of arguments in MACRO 8) No support for declaring variables in blocks . and more .. all...
Post a Comment
Read more