Swap nodes of a linked list

Qn:
Write a function to swap the adjacent nodes of a singly linked list.i.e. If the list has nodes as 1,2,3,4,5,6,7,8, after swapping, the list should be 2,1,4,3,6,5,8,7

Image from: https://tekmarathon.com

Though the question looks simple enough, it is tricky because you don't just swap the pointers. You need to take care of links as well.

So let us try to understand how to go about it.

• Take two adjacent nodes p1 and p2
• Let prevnode be previous node of p1
• Now link prevnode to p2
• Link p2 to p1
• Link p1 to next node of p2

So the code will be

prevnode->next  = p2;
p1->next = p2->next;
p2->next = p1;

But what about the start node or head?

• head node does not have previous node
• If we swap head with second node, modified head should be sent back to caller

 To take care of swapping first and second nodes, we can write

p1 = head;
p2 = head->next;
p1->next = p2->next;
p2->next = p1;
head = p2;

 Now we are ready to write the function. Write the second code block and then write first code block in a while loop.

 NODEPTR swap_nodes(NODEPTR head)
{
    NODEPTR prevnode = head;   
    NODEPTR temp = head->next;
    head->next = temp->next;
    temp->next = head;
    head = temp;
    temp = head->next->next;
    prevnode = head->next;    
    while(temp!=NULL)
    {
  NODEPTR p1,p2;
         p1 = temp;
         p2 = p1->next;
         if(p2!=NULL){
         prevnode->next = p2;
         p1->next = p2->next;
         p2->next = p1;         
         }
         prevnode= temp;
         temp = temp->next; 
     }
     return head;
}
 

Finally, to use this function, call it as

head = swap_nodes(head);

And here is the driver program.

#include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int n;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;  
  
 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->n = value;  
   return temp;  
 } 
  
 NODEPTR append_node(NODEPTR head, NODEPTR newnode)  
 {  
    NODEPTR temp = head;
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
 temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
 
 void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->n);  
     temp = temp->next;  
   }  
   printf("\n");
 } 
 NODEPTR swap_nodes(NODEPTR head)
{
    NODEPTR prevnode = head;
   
    NODEPTR temp = head->next;
    head->next = temp->next;
    temp->next = head;
    head = temp;
    temp = head->next->next;
    prevnode = head->next;
    
    while(temp!=NULL)
    {
  NODEPTR p1,p2;
         p1 = temp;
         p2 = p1->next;
         if(p2!=NULL){
         prevnode->next = p2;
         p1->next = p2->next;
         p2->next = p1;         
         }
         prevnode= temp;
         temp = temp->next; 
     }
     return head;
} 
 int main()  
 {  
     NODEPTR head;  
     NODEPTR newnode,dnode;  
     
     //initialize head  
     head =  NULL;  
      
     while(1){
       int value;  
       NODEPTR newnode;  
       printf("node value (-1 to stop)=");  
       scanf("%d",&value); 
       if(value==-1) 
   break; 
       newnode = create_node(value);  
       head = append_node(head,newnode);      
     }
     printf("The linked list now is ");  
     display_nodes(head);
     head = swap_nodes(head);
  printf("The linked list now is ");  
     display_nodes(head);           
 }