How to swap nodes in a linked list without Swapping data?

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.

Swap nodes

This may seem like a simple matter, but it is an interesting question because you need to handle the following cases:

  1. x and y may not or may be adjacent.
  2. X or y can be the main node.
  3. X or y can be the last node.
  4. 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:

Swap nodes

Swap nodes

Swap nodes

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:

Swap nodes

Swap nodes

Swap nodes

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

Recommended Articles:

  1. How to reverse a linked list?
  2. How to write C functions that modify head pointer of a Linked List?
  3. Find Length of a Linked List (Iterative and Recursive)?
  4. A Programmer’s approach of looking at Array vs. Linked List
  5. How to delete a node in a linked list at a given Location?

References:

Help Me Please: If you found any error in the content or example please let us know by comment also write your suggestion or if any doubt in the concept please feel free to write us in the comment section.

Practice your Code online here

(Visited 84 times, 1 visits today)

0 0 vote
Article Rating
Subscribe
Notify of
6 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
trackback

[…] How to swap nodes in a linked list without Swapping data? […]

trackback

[…] How to swap nodes in a linked list without Swapping data? […]

trackback

[…] How to swap nodes in a linked list without Swapping data? […]

trackback

[…] How to swap nodes in a linked list without Swapping data? […]

trackback

[…] How to swap nodes in a linked list without Swapping data? […]

trackback

[…] How to swap nodes in a linked list without Swapping data? […]

You cannot copy content of this page
Scroll Up
6
0
Would love your thoughts, please comment.x
()
x

  • Name

  • Minimum length of 8 characters.