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

Interactive C program to implement stack using doubly linked list

shiv@ubuntu:~/ds/stack$ cat stack.c /*  * Copy right by Shiv Yaragatti  * you are free to use, modify  and redistribute code on own risk  * Interactive C Program to implement STACK using Doubly linked list  */ #include "header.h" struct stack { int data; struct stack *next; struct stack *prev; }; typedef struct stack *S; /*Push elements in to stack */ void push(S *stack) {   int e;   S temp;   temp=malloc(sizeof(struct stack));   if(!temp){      printf("Can't allocate memory\n");      return;  }  printf("Enter element to push\n");  scanf("%d", &e);  temp->data=e;  if(*stack == NULL){     temp->next = temp->prev = NULL;     *stack=temp;  } else {    temp->next = *stack;    (*stack)->prev = temp;    temp->prev = NULL;    *stack=temp;  } } /* Display elements in the stack */...
Post a Comment
Read more