Swap Nodes in a Linked List Without Swapping Data

In this blog, we will learn about the famous problem of swap the nodes in a linked list without swapping data, we have given two keys in a linked list and the task is to swap the nodes in a linked list without swapping data. p>

Swap Nodes of Linked List Without Swapping Data

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 the linked list will have the same data.

Understanding How to Swap Nodes:

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 to swap the nodes of linked list without swapping data

Swapping nodes seem 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 to swap the nodes in a linked list without swapping data

• 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 <stdio.h>
#include <stdlib.h>
 
/* A linked list node */
struct Node {
    int data;
    struct Node* next;
};
 
void swapNodes(struct Node** head_ref, int x, int y)
{
    if (x == y)
        return;
 
    struct Node *prevX = NULL, *currX = *head_ref;
    while (currX && currX->data != x) {
        prevX = currX;
        currX = currX->next;
    }
 
    struct Node *prevY = NULL, *currY = *head_ref;
    while (currY && currY->data != y) {
        prevY = currY;
        currY = currY->next;
    }
 
    if (currX == NULL || currY == NULL)
        return;
 
    if (prevX != NULL)
        prevX->next = currY;
    else // Else make y as new head
        *head_ref = currY;
 
    // If y is not head of linked list
    if (prevY != NULL)
        prevY->next = currX;
    else // Else make x as new head
        *head_ref = currX;
 
    // Swap next pointers
    struct Node* temp = currY->next;
    currY->next = currX->next;
    currX->next = temp;
}
 
/* Function to add a node at the beginning of List */
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
 
    /* put in the data  */
    new_node->data = new_data;
 
    /* link the old list off the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
/* Function to print nodes in a given linked list */
void printList(struct Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
/* Driver program to test above function */
int main()
{
    struct Node* start = NULL;
 
    /* The constructed linked list is:
     1->2->3->4->5->6->7 */
    push(&start, 7);
    push(&start, 6);
    push(&start, 5);
    push(&start, 4);
    push(&start, 3);
    push(&start, 2);
    push(&start, 1);
 
    printf("\n Linked list before calling swapNodes() ");
    printList(start);
 
    swapNodes(&start, 4, 3);
 
    printf("\n Linked list after calling swapNodes() ");
    printList(start);
 
    return 0;
}

#include <bits stdc++.h="">
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();
    }
}

class LinkedList(object):
	def __init__(self):
		self.head = None

	class Node(object):
		def __init__(self, d):
			self.data = d
			self.next = None

	def swapNodes(self, x, y):

		if x == y:
			return

		prevX = None
		currX = self.head
		while currX != None and currX.data != x:
			prevX = currX
			currX = currX.next

		prevY = None
		currY = self.head
		while currY != None and currY.data != y:
			prevY = currY
			currY = currY.next

		if currX == None or currY == None:
			return
		if prevX != None:
			prevX.next = currY
		else:
			self.head = currY

		if prevY != None:
			prevY.next = currX
		else: 
			self.head = currX

		temp = currX.next
		currX.next = currY.next
		currY.next = temp

	def push(self, new_data):

		new_Node = self.Node(new_data)
		new_Node.next = self.head
		self.head = new_Node

	def printList(self):
		tNode = self.head
		while tNode != None:
			print(tNode.data , end =" ")
			tNode = tNode.next


llist = LinkedList()

llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
print("Linked list before calling swapNodes() ")
llist.printList()
llist.swapNodes(2, 4)
print("\nLinked list after calling swapNodes() ")
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.

Conclusion

In this article, we have discussed and explained the approach of how we can perform the operation of swapping the nodes in a linked list without swapping data. If you want to practice solving more problems on linked lists, feel free to solve them at PrepBytes.

FAQs

1. What is swapping in data structures?

Swapping means any process can be temporarily swapped from main memory to secondary memory.

2. Explain swapping two nodes?

Swapping refers to the exchange of two pieces of data. For example, in programming data may be swapped between two variables, or things may be swapped between two people.

3. What is the syntax of swap() function?

Syntax of swap() function:
Void swap(var_1, var_2)
If we assign the values to variables or pass user-defined values, it will swap the values of variables but the value of variables will remain the same at the actual place.