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

**What is swapping in data structures?****Explain swapping two nodes?****What is the syntax of swap() function?**

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

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.

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.