Tag: 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. 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 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 data 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 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 data 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 printList(); swapNodes(&start, 6, 1); cout 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/

Tag: Swap nodes in a linked list without Swapping data

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

Categories

Pages

Programmer’s Academy