How to swap two nodes in a linked list is a popular problem in data structure. In this post I will explain how to swap two nodes in a linked list. I will explain to swap two nodes without swapping data in a linked list.
Write a C program to create a linked list and accept two node position from user. The program should swap two nodes in linked list without swapping their data.
Required knowledge
Singly linked list, Pointers, Structures, Functions, Dynamic Memory Allocation
How to swap two nodes in a linked list?
Step by step descriptive logic to swap two nodes in a singly linked list.
- Create a singly linked list and input node data from user. Store reference of first node in a variable say head.
Initially the list should look similar to following.
- Input positions to swap from user. Store them in two variables say pos1 and pos2.
- Check for invalid swap positions and return from function if swap positions invalid.
- Initialize four variables of node type with
NULL. Sayprev1 = NULL;,node1 = NULL;,prev2 = NULL;andnode2 = NULL;. Where node1 and node2 will store nodes to swap. And prev1, prev2 will store node previous to nodes to swap. - Initialize another variable of node type. It should point to the first node in the list. Say
temp = list;. - Next we need to locate the nodes to swap and node previous to them. Run a loop from 1 to maximum position to swap.
- Inside loop update
prev1 to temp if (i == pos1 – 1) (where i is loop counter variable).
next1 to temp if (i == pos1).
prev1 to temp if (i == pos2 – 1).
next2 to temp if (i == pos2). - Move to next element i.e.
temp = temp->next;for each iteration. And also increment loop counter variable. - Once the loop completes you will have links of nodes to swap. In the below image, suppose we want to swap 2 and 4th element.
- Verify that you have link to nodes to swap using
if (node1 != NULL && node2 != NULL). If it satisfies then first adjust links for node previous to actual swap nodes.Link
prev1->nextwith node2 andprev2->nextwith node1. Link them only if prev1 and prev2 are notNULL.
- Swap next link in both nodes accordingly.
node1->next = node2->next;and vice versa.
. - Adjust head node if needed. Below is the final list after swapping.
Program to swap two nodes in a linked list
/**
* C program to swap two nodes in a linked list.
*/
#include <stdio.h>
#include <stdlib.h>
/* Node structure */
struct node
{
int data; // Data
struct node *next; // Address
} * head;
/* Function declaration */
void createList(int n);
void displayList();
int count(struct node *list);
int swap(struct node *list, int pos1, int pos2);
int main()
{
int n, pos1, pos2;
// Input node count to create
printf("Enter number of node to create: ");
scanf("%d", &n);
createList(n);
// Display list
printf("\n\nData in list before swapping: \n");
displayList();
printf("\nEnter first node position to swap: ");
scanf("%d", &pos1);
printf("\nEnter second node position to swap: ");
scanf("%d", &pos2);
if (swap(head, pos1, pos2) == 1)
{
printf("\nData swapped successfully.\n");
printf("Data in list after swapping %d node with %d: \n", pos1, pos2);
displayList();
}
else
{
printf("Invalid position, please enter position greater than 0 and less than nodes in list.\n");
}
return 0;
}
/**
* Create a list of n nodes
*/
void createList(int n)
{
struct node *newNode, *temp;
int data, i;
head = malloc(sizeof(struct node));
/*
* Unable to allocate memory, hence exit from app.
*/
if (head == NULL)
{
printf("Unable to allocate memory. Exiting from app.");
exit(0);
}
/* Input head node data from user */
printf("Enter data of node 1: ");
scanf("%d", &data);
head->data = data; // Link data field with data
head->next = NULL; // Link address field to NULL
temp = head;
/*
* Create n nodes and add to the list
*/
for (i = 2; i <= n; i++)
{
newNode = malloc(sizeof(struct node));
/* If memory is not allocated for newNode */
if (newNode == NULL)
{
printf("Unable to allocate memory. Exiting from app.");
exit(0);
}
printf("Enter data of node %d: ", i);
scanf("%d", &data);
newNode->data = data; // Link data field of newNode
newNode->next = NULL; // The newNode should point to nothing
temp->next = newNode; // Link previous node i.e. temp to the newNode
temp = temp->next;
}
}
/**
* Display entire list
*/
void displayList()
{
struct node *temp;
/*
* If the list is empty i.e. head = NULL,
* dont perform any action and return.
*/
if (head == NULL)
{
printf("List is empty.\n");
return;
}
temp = head;
while (temp != NULL)
{
printf("%d, ", temp->data); // Print data of current node
temp = temp->next; // Move to next node
}
printf("\n");
}
/**
* Counts total number of nodes in a linked list.
* @param *list Pointer to head node of linked list.
* @returns Total count of nodes in list.
*/
int count(struct node *list)
{
int nodes = 0;
while (list != NULL)
{
nodes++;
list = list->next;
}
return nodes;
}
/**
* Function to swap two nodes of a linked list
* @param *list Pointer to head node of the list
* @param pos1 Position of first node to swap
* @param pos2 Position of second node to swap
* @returns 1 on success, -1 on failure if swap
* positions are invalid.
*/
int swap(struct node *list, int pos1, int pos2)
{
struct node *node1, *node2, *prev1, *prev2, *temp;
int i;
// Get the far position among both
const int maxPos = (pos1 > pos2) ? pos1 : pos2;
// Get total nodes in the list
const int totalNodes = count(list);
// Validate swap positions
if ((pos1 <= 0 || pos1 > totalNodes) || (pos2 <= 0 || pos2 > totalNodes))
{
return -1;
}
// If both positions are same then no swapping required
if (pos1 == pos2)
{
return 1;
}
// Identify both nodes to swap
i = 1;
temp = list;
prev1 = NULL;
prev2 = NULL;
// Find nodes to swap
while (temp != NULL && (i <= maxPos))
{
if (i == pos1 - 1)
prev1 = temp;
if (i == pos1)
node1 = temp;
if (i == pos2 - 1)
prev2 = temp;
if (i == pos2)
node2 = temp;
temp = temp->next;
i++;
}
// If both nodes to swap are found.
if (node1 != NULL && node2 != NULL)
{
// Link previous of node1 with node2
if (prev1 != NULL)
prev1->next = node2;
// Link previous of node2 with node1
if (prev2 != NULL)
prev2->next = node1;
// Swap node1 and node2 by swapping their
// next node links
temp = node1->next;
node1->next = node2->next;
node2->next = temp;
// Make sure to swap head node when swapping
// first element.
if (prev1 == NULL)
head = node2;
else if (prev2 == NULL)
head = node1;
}
return 1;
}Enter number of node to create: 5 Enter data of node 1: 10 Enter data of node 2: 20 Enter data of node 3: 30 Enter data of node 4: 40 Enter data of node 5: 50 Data in list before swapping: 10, 20, 30, 40, 50, Enter first node position to swap: 2 Enter second node position to swap: 4 Data swapped successfully. Data in list after swapping 2 node with 4: 10, 40, 30, 20, 50,