Swap nodes in a linked list without swapping data

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we will be discussing how we can swap nodes directly by changing links rather than swapping out the data. We will be given a linked list and two keys say x and y, and we have to swap the nodes of the linked list having these keys as data.

Note: All the keys in the linked list are unique, i.e. no two nodes in linked list will have the same data.

Problem Statement Understanding:

Let’s try to understand what the actual problem is, so basically here, we will be given a linked list and two keys x and y. We will have to iterate the linked list and search for the nodes with keys x and y. Once we got the nodes with the keys x and y, we will have to swap these nodes. We can swap nodes of linked list either by swapping their data or by changing the links (swapping nodes). Here we will be swapping the nodes by changing the links of the nodes.

Input:

Keys are 2 and 4 (x=2 and y=4).

Output (After swapping the nodes):

Which method of swapping is more efficient, swapping by data or swapping by nodes?

In LinkedList, if we have to swap the data of two nodes, it’s easy if there are fewer fields, and it would also take less time but if the data inside the nodes is large then swapping that amount of data can limit the speed of the process. For this reason, swapping nodes is preferred.

Now let’s move to the approach section, there we will see how we will solve the above problem of searching the nodes and swapping.

Approach

Swapping nodes seems easy if the nodes to be swapped are adjacent, but then it becomes difficult for the following cases:

  • The first case is when x and y are not adjacent.
  • Or may be either of x and y is head nodes.
  • Or maybe either x or y is the last node.
  • And there can be a case where x and/or y may not even be present in the linked list.

The idea is to search for the two nodes with keys x and y, if any of them is not present then return null otherwise change the next pointers of the two nodes.

Algorithm

  • Search for x and y nodes in the LinkedList.
  • If any of them is NULL, return.
  • Take 4 pointers as previousX, currentX, previousY, currentY to denote the previous and current nodes of x and y respectively.
  • If x is not head of the linked list, then change previousX->next = currentY and if x is head of the linked list then make node y as the new head of the linked list.
  • If y is not head of the linked list, then change previousY->next = currentX and if y is the head of the linked list then make node x as the new head of the linked list.
  • Finally, swap the next pointers of the current nodes as currentX->next to currentY->next.

Dry Run

Let me dry run this for a small test case, then it will be much clearer to understand. In the following example, we have a linked list, and we need to swap the two nodes having keys as 2 and 4.

Code Implementation


#include 
using namespace std;
class Node {
public:
    int data;
    Node* next;
};

void swapNodes(Node** head_ref, int x, int y)
{
    if (x == y)
        return;
    Node *previousX = NULL, *currentX = *head_ref;
    while (currentX && currentX->data != x) {
        previousX = currentX;
        currentX = currentX->next;
    }
    Node *previousY = NULL, *currentY = *head_ref;
    while (currentY && currentY->data != y) {
        previousY = currentY;
        currentY = currentY->next;
    }
    if (currentX == NULL || currentY == NULL)
        return;
    if (previousX != NULL)
        previousX->next = currentY;
    else
        *head_ref = currentY;

    if (previousY != NULL)
        previousY->next = currentX;
    else 
        *head_ref = currentX;

    Node* temp = currentY->next;
    currentY->next = currentX->next;
    currentX->next = temp;
}
void push(Node** head_ref, int new_data)
{
    Node* new_node = new Node();

    
    new_node->data = new_data;

    new_node->next = (*head_ref);

    (*head_ref) = new_node;
}
void printList(Node* node)
{
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
int main()
{
    Node* start = NULL;
    push(&start, 5);
    push(&start, 4);
    push(&start, 3);
    push(&start, 2);
    push(&start, 1);
    swapNodes(&start, 2, 4);
    printList(start);
    return 0;
}


class Node {
    int data;
    Node next;
    Node(int d)
    {
        data = d;
        next = null;
    }
}

class LinkedList {
    Node head; 
    public void swapNodes(int x, int y)
    {
        if (x == y)
            return;
        Node prevX = null, currX = head;
        while (currX != null && currX.data != x) {
            prevX = currX;
            currX = currX.next;
        }

        Node prevY = null, currY = head;
        while (currY != null && currY.data != y) {
            prevY = currY;
            currY = currY.next;
        }
        if (currX == null || currY == null)
            return;

        if (prevX != null)
            prevX.next = currY;
        else 
            head = currY;

        if (prevY != null)
            prevY.next = currX;
        else 
            head = currX;

        Node temp = currX.next;
        currX.next = currY.next;
        currY.next = temp;
    }

    public void push(int new_data)
    {
        Node new_Node = new Node(new_data);

        new_Node.next = head;

        head = new_Node;
    }

    public void printList()
    {
        Node tNode = head;
        while (tNode != null) {
            System.out.print(tNode.data + " ");
            tNode = tNode.next;
        }
    }
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
        llist.push(5);
        llist.push(4);
        llist.push(3);
        llist.push(2);
        llist.push(1);

        llist.swapNodes(2, 4);
        llist.printList();
    }
}

Output

1 4 3 2 5

Time Complexity: O(n), where n is the number of nodes present in the LinkedList.

Space Complexity: O(1), no extra space is used.

In this blog, we have discussed and explained how we can swap two nodes of a linked list by swapping their link pointers instead of swapping their data. If you want to practice more questions on linked lists, feel free to solve them at Linked List.

Previous post LinkedList implementation in JavaScript
Next post Delete N nodes after M nodes of a Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *