Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Swap Nodes in a Linked List Without Swapping Data

Last Updated on July 27, 2023 by Mayank Dham

A linked list is a type of data structure that stores a sequence of elements, each of which points to the next element in the sequence. Linked lists are made up of nodes, each of which contains data as well as a pointer to the next node in the sequence. The first node is referred to as the head node, and the last node is referred to as the tail node. Because they can be dynamically resized, linked lists are commonly used in programming to implement other data structures such as stacks, queues, and hash tables. In this section, we will be discussing how we swap two nodes in linked list

.

## How to Swap Two Nodes in 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 swapping nodes in a linked list Works

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 two nodes in 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

if (prevY != NULL)
prevY->next = currX;
else // Else make x as new head

// 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 */

/* move the head to point to the 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

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

Node* temp = currentY->next;
currentY->next = currentX->next;
currentX->next = temp;
}
{
Node* new_node = new Node();

new_node->data = new_data;

}
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;
}
}

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

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

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

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

}

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

llist.swapNodes(2, 4);
llist.printList();
}
}
```
```
def __init__(self):

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

def swapNodes(self, x, y):

if x == y:
return

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

prevY = None
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:

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

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

def push(self, new_data):

new_Node = self.Node(new_data)

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

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

Swapping nodes in a linked list is a fundamental operation that involves exchanging the positions of two nodes within the structure. This process is essential for reorganizing data, sorting the list, or implementing various algorithms without modifying the actual data stored in the nodes. Swapping nodes can be efficiently achieved by changing the links between the nodes rather than swapping their data. By employing this approach, we can efficiently swap nodes in a linked list without the need for extra memory space. This technique is particularly useful when dealing with large data elements or when there is a need for bidirectional traversal within the linked list.
PrepBytes.