C program to swap two nodes in a linked list

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.

  1. Create a singly linked list and input node data from user. Store reference of first node in a variable say head.
    How to swap two nodes in a linked list 1

    Initially the list should look similar to following.

  2. Input positions to swap from user. Store them in two variables say pos1 and pos2.
  3. Check for invalid swap positions and return from function if swap positions invalid.
  4. Initialize four variables of node type with NULL. Say prev1 = NULL;, node1 = NULL;, prev2 = NULL; and node2 = NULL;. Where node1 and node2 will store nodes to swap. And prev1, prev2 will store node previous to nodes to swap.
  5. Initialize another variable of node type. It should point to the first node in the list. Say temp = list;.
  6. Next we need to locate the nodes to swap and node previous to them. Run a loop from 1 to maximum position to swap.
  7. 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).
  8. Move to next element i.e. temp = temp->next; for each iteration. And also increment loop counter variable.
  9. 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.
    How to swap two nodes in a linked list 2
  10. 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->next with node2 and prev2->next with node1. Link them only if prev1 and prev2 are not NULL.

    How to swap two nodes in a linked list 3

  11. Swap next link in both nodes accordingly. node1->next = node2->next; and vice versa.
    How to swap two nodes in a linked list 4.
  12. Adjust head node if needed. Below is the final list after swapping.
    How to swap two nodes in a linked list 5

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,