Given a linked list and two keys in it, swap the node for two given keys. You need to change the link to replace the node. If the data contains many fields, exchanging data at the node can be expensive in many situations.
It can assume that all keys in linked list are separate.
This may seem like a simple matter, but it is an interesting question because you need to handle the following cases:
- x and y may not or may be adjacent.
- X or y can be the main node.
- X or y can be the last node.
- x and/or and may not be present in the linked list.
How to write clean code that handles all of the above possibilities.
It is highly recommended to minimize your browser and try it yourself first.
The idea of looking for x and y first in a given linked list. If any of them don’t exist, they will come back. Keeps track of current and previous pointers while searching for x and y. First change the next to the previous pointer, then change the next to the current pointer.
For example:
Here Code:
#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 *prevX = NULL, *currX = *head_ref;
while (currX && currX->data != x) {
prevX = currX;
currX = currX->next;
}
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
*head_ref = currY;
if (prevY != NULL)
prevY->next = currX;
else
*head_ref = currX;
Node* temp = currY->next;
currY->next = currX->next;
currX->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, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
cout << "Linked list before calling swapNodes() ";
printList(start);
swapNodes(&start, 4, 3);
cout << "\nLinked list after calling swapNodes() ";
printList(start);
return 0;
}
Optimization:
The above code can be optimized to find x and y in a single scan. Two loops are used to simplify the program.
Simpler approach:
For example:
Here Code:
#include <iostream>
using namespace std;
class Node {
public:
int data;
class Node* next;
Node(int val, Node* next)
: data(val)
, next(next)
{
}
void printList()
{
Node* node = this;
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
};
void push(Node** head_ref, int new_data)
{
(*head_ref) = new Node(new_data, *head_ref);
}
void swap(Node*& a, Node*& b)
{
Node* temp = a;
a = b;
b = temp;
}
void swapNodes(Node** head_ref, int x, int y)
{
if (x == y)
return;
Node **a = NULL, **b = NULL;
while (*head_ref) {
if ((*head_ref)->data == x) {
a = head_ref;
}
else if ((*head_ref)->data == y) {
b = head_ref;
}
head_ref = &((*head_ref)->next);
}
if (a && b) {
swap(*a, *b);
swap(((*a)->next), ((*b)->next));
}
}
int main()
{
Node* start = NULL;
push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
cout << "Linked list before calling swapNodes() ";
start->printList();
swapNodes(&start, 6, 1);
cout << "Linked list after calling swapNodes() ";
start->printList();
}
References:
- https://tutorialspoint.dev/data-structure/linked-list/swap-nodes-in-a-linked-list-without-swapping-data
- https://github.com/sidgupta234/GFG/blob/master/Linked%20List/swap-nodes-in-a-linked-list-without-swapping-data.cpp
- https://www.codespeedy.com/swap-nodes-in-a-linked-list-without-swapping-data-in-cpp/
- https://thecodingsimplified.com/swap-nodes-of-given-values-without-swapping-data/
