ronith
7/7/2018 - 10:41 AM

Swap nodes in a linked list without swapping data

Given a linked list and two keys in it, swap nodes for two given keys. Nodes should be swapped by changing links. Swapping data of nodes may be expensive in many situations when data contains many fields.

It may be assumed that all keys in linked list are distinct.

Examples:

Input: 10->15->12->13->20->14, x = 12, y = 20 Output: 10->15->20->13->12->14

Input: 10->15->12->13->20->14, x = 10, y = 20 Output: 20->15->12->13->10->14

Input: 10->15->12->13->20->14, x = 12, y = 13 Output: 10->15->13->12->20->14

Swap nodes in a linked list without swapping data.cpp
content_copyfile_download
// https://www.geeksforgeeks.org/swap-nodes-in-a-linked-list-without-swapping-data/
#include <bits/stdc++.h>
using namespace std;

struct linked_list {
    int data;
    struct linked_list* next;
};
typedef struct linked_list node;

void print (node* n) {
    while (n != NULL) {
        cout<< n->data<< "->";
        n = n->next;
    }
}

node* insert(node* head, int n) {
    node* temp = (node*)malloc(sizeof(node*));
    temp->data = n;
    temp->next = head;
    head = temp;
    return head;
}

node* swap (node* head,int x, int y) {
    node *prev1=NULL, *temp1=head, *prev2=NULL, *temp2=head;
    while (temp1 && temp1->data != x){
        prev1 = temp1;
        temp1 = temp1->next;
    }
    while (temp2 && temp2->data != y){
        prev2 = temp2;
        temp2 = temp2->next;
    }

    if (prev1 != NULL)
        prev1->next = temp2;
    else
        head=temp2;
    if (prev2 != NULL)
        prev2->next = temp1;
    else
        head = temp1;
    node* temp = temp1->next;
    temp1->next = temp2->next;
    temp2->next = temp;
    return head;
}

int main() {
    int n,x,y;
    node* head = NULL;
    while (true) {
        cout<< "Enter the elements, and -999 to stop: ";
        cin>>n;
        if (n==-9)
            break;
        else
            head=insert(head,n);
    }
    print(head);
    cout<< "Enter x and y: ";
    cin>>x>>y;
    head=swap(head,x,y);
    cout<< "\n";
    print(head);
}