Question

Write a subroutine named swap in C thatswaps two nodes in a linked list. The first node should not be able to change places. The nodes are given by:

Struct nodeEl {

int el;

struct nodeEl * next;

};

typdef struct nodeEl node;

The list header (of type node *) is the first parameter of the subroutine. The second and third parameters consist of integers and are the places in the list where the nodes are to change places. The subroutine should be written in such a way that the nodes change places (and not the elements in the nodes). A suitable precondition for calling the subroutine is that the two places must be greater than 1 and less than or equal to the number of list elements. The subroutine must be written without using library functions (the exceptions are malloc and free). It is allowed to define help functions. Also write an explanation of how the subroutine works

Answer 1

Program

#include<stdio.h>
#include<stdlib.h>

/* A linked list node */
struct nodeEl
{
   int el;
   struct nodeEl *next;
};

typedef struct nodeEl node;

/* Function to swap nodes x and y in linked list by
changing links */
void swap(node **head_ref, int x, int y)
{
   // Nothing to do if x and y are same
   if (x == y)
   {
       printf("Sorry , swap can't occur as you have entered same indexes to be swapped, try again !!\n");
       return;  
   }
  
   if(x==1 || y==1)
   {
       printf("Sorry , swap can't occur as you have entered index 1 that can't be swapped, try again !!\n");
       return;  
   }
  
   // Search for x (keep track of prevX and CurrX )
   node *prevX = NULL, *currX = *head_ref;
   int cntx=1,cnty=1;
   while(cntx!=x)
   {
       prevX=currX;
       currX = currX->next;
       cntx++;
   }
  
   // Search for y (keep track of prevY and CurrY )
   node *prevY = NULL, *currY = *head_ref;
   while(cnty!=y)
   {
       prevY = currY;
       currY = currY->next;
       cnty++;
   }
  
   // If x is not head of linked list
   if (prevX != NULL)
       prevX->next = currY;
   else // Else make y as new head
       *head_ref = currY;
  
   // If y is not head of linked list
   if (prevY != NULL)
       prevY->next = currX;
   else // Else make x as new head
       *head_ref = currX;
  
   // Swap next pointers
   node *temp = currY->next;
   currY->next = currX->next;
   currX->next = temp;
}

/* Function to add a node at the beginning of List */
void push(node** head_ref, int new_data)
{
   /* allocate node */
   node * new_node = (node *) malloc(sizeof(node));

   /* put in the data */
   new_node->el = new_data;

   /* link the old list off the new node */
   new_node->next = (*head_ref);

   /* move the head to point to the new node */
   (*head_ref) = new_node;
}

/* Function to print nodes in a given linked list */
void printList(node *head)
{
   while(head != NULL)
   {
       printf("%d ", head->el);
       head = head->next;
   }
}

/* Driver program to test above function */
int main()
{
   node *start = NULL;

   /* The constructed linked list is:
   1->2->3->4->5->6->7
   push(&start, 77);
   push(&start, 63);
   push(&start, 51);
   push(&start, 44);
   push(&start, 39);
   push(&start, 22);
   push(&start, 10);
   */
  
   int i,n,value,index1,index2;
   printf("Enter the total no. of nodes to inserted = ");
   scanf("%d",&n);
  
   /* The constructed linked list */
   for(i=0;i<n;i++)
   {
       scanf("%d",&value);
       push(&start, value);
   }

   printf("\nLinked list before calling swap() ");
   printList(start);
  
   printf("\nEnter the two indexes that are to be swapped (index starts from 1) :-\n");
   scanf("%d",&index1);
   scanf("%d",&index2);
   swap(&start, index1, index2);

   printf("\nLinked list after calling swap() ");
   printList(start);

   return 0;
}

Outputs :-

Code Explanation :-
1. Firstly I have created a start node that is the head of the linked list and is NULL in the beginning.Then geeting the input from user for how many nodes he/she wants to have in a linked list (it is variable n).
2.Then I have taken the value for each node from the user using the loop.
3.Then taking two indexes as input from the user in variables namely index1 and index2 which he/she wants to swap.
4.Then calling swap function/subroutine and passing the start/head of linked list and both the indexes.
5.Then in swap() , I have checked that both the indexes entered by user are same or different as if he/she had entered same value then swap can't be done.
6.If both indexes are distinct then the program checks that the index1 and index2 variable must not equal to 1.
7.If it satisfies both the above conditions then it does the swapping.
8.At last , the program prints the list again to show to changes.