How to swap nodes in a linked list without swapping their data

A linked list is a data structure made of a chain of node objects. Each node contains a value and a pointer to the next node in the chain.

To swap two nodes of a linked list, we can either just swap their data values or manipulate the pointers in the chain to move the actual nodes themselves. The first approach works well if there are very few data fields. However, if there are many data fields in a node, it gets computationally expensive to swap nodes by swapping their values (since a lot of individual swaps need to occur). In such cases, it is important to know how to swap nodes by manipulating pointers. In this Answer, we'll explore how this latter approach can be used to achieve this.

Note: To learn more about how a linked list can be implemented, refer to this link.

Possible cases to consider

When swapping 2 nodes, x and y, in a linked list, there are a few cases that can arise:

  • X and y are adjacent to each other, and:

    • One of x or y is the head node of the list.

    • None of x or y is either a head node or a tail node.

  • X and y are not adjacent to each other, and:

    • One of x or y is the head node of the list.

    • None of x or y is either a head node or a tail node.

  • X or y don't even exist in the linked list.

Hence, our solution must be general enough to incorporate all of these cases.

Algorithm

To swap x and y, we must search for them in the linked list. To do this, we traverse the linked list from start to end. While searching for x and y, we also keep a track of 2 new pointers previous_of_x and previous_of_y , which point to the nodes occurring before x and y, respectively (both these pointers are initialized to NULL before the search begins). After the search, if we find that at least one of x or y doesn't exist in the list, we can stop and return since no swapping can happen in this case.

If both x and y are found, we can get ready to swap them by following the steps below:

  1. If x is the head of the linked list (this will happen when previous_of_x is NULL):

    • Set the head pointer of the list to y.

  2. If x is not the head of the linked list:

    • Set the next pointer of previous_of_x to y.

  3. If y is the head of the linked list (this will happen when previous_of_y is NULL):

    • Set the head pointer of the list to x.

  4. If y is not the head of the linked list:

    • Set the next pointer of previous_of_y to x.

  5. Set the next pointer of x to the node currently to the next of y (x->next = y->next).

  6. Set the next pointer of y to the node that was previously to the next of x.

The examples below demonstrate how this would work.

Example 1: Neither x nor y is the head node:

1 of 14

Example 2: y is the head node:

1 of 14

Code Example

#include <iostream>
using namespace std;
class Node {
public:
    int value;
    Node* next;
    Node()
    {
      next = NULL ;
    }
    
    Node(int val)
    {
      value = val ;
      next = NULL ;
    }
};
 
class LinkedList
{
public:
  Node* head;
  LinkedList(Node* to_make_head)
  {
    head = to_make_head ;
  }
  
  void swapNodes(int val_x, int val_y)
  {
    // search for x and find previous_of_x
    Node* previous_of_x = NULL;
    Node* x = head;
    while (1) 
    {
      if(x == NULL || x->value == val_x)
      {
        break;
      }
      previous_of_x = x;
      x = x->next;
    }
    // search for y and find previous_of_y
    Node* previous_of_y = NULL; 
    Node* y = head;
    while (1) 
    {
      if(y == NULL || y->value == val_y)
      {
        break ;
      }
      previous_of_y = y;
      y = y->next;
    }
    // if one of x or y don't exist, then there is nothing to swap
    if (x == NULL || y == NULL)
    {
      return;
    }
    // If x is the head of the linked list
    if (previous_of_x == NULL)
    {
      head = y;
    }
    else // if x is not the head of the list
    {
      previous_of_x->next = y;
    }
    // If y is the head of the linked list
    if(previous_of_y == NULL)
    {
      head = x;
    } 
    else // if y is not the head of the list
    {
      previous_of_y->next = x;
    }
    // changing the next pointer of x and y
    Node* temp = y->next;
    y->next = x->next;
    x->next = temp;
  }
  void push(int new_data)
  {
    Node* new_node = new Node();
    new_node->value = new_data;
    new_node->next = head;
    head = new_node;
  }
  void printList()
  {
    Node* node = head;
    while (node != NULL) 
    {
      cout << node->value << " ";
      node = node->next;
    }
  }
};
 
 
 
/* Driver program to test above function */
int main()
{
  Node* head = new Node(7);
  LinkedList example_list(head);
  example_list.push(6);
  example_list.push(5);
  example_list.push(4);
  example_list.push(3);
  example_list.push(2);
  example_list.push(1);
  // The constructed linked list is:
  // 1->2->3->4->5->6->7 */
 
  cout << "Linked list before calling swapNodes() ";
  example_list.printList();
  example_list.swapNodes(2, 6);
  cout << "\nLinked list after calling swapNodes() ";
  example_list.printList();
  return 0;
}

Explanation

A few key lines from the implemented algorithm above are explained below.

  • Lines 34–44: We initialize previous_of_x to NULL. At the end of each iteration of the loop, previous_of_x points to x and then x is updated to point at x->next. This way, previous_of_x is always the node occurring before node x , and in case x is the head node, previous_of_x never gets updated and still points to NULL.

  • Lines 47–57: We initialize previous_of_y to NULL. At the end of each iteration of the loop, previous_of_y points to y and then y is updated to point at y->next. This way, previous_of_y is always the node occurring before the node y , and in case y is the head node, previous_of_y never gets updated and still points to NULL.

  • Lines 60–82: We deal with the cases of x or y being the head node or not, as discussed above in the algorithm.

  • Lines 86–88: After storing the node currently to the next of x in temp, we set the next pointer of x to the node currently to the next of y, and then set the next pointer of y to temp.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved