Question

Please use C++ and linked list to solve this problem

Linked list 1 -> 2 -> 3 -> 4 -> 5-> 6 ->7

replaceNode( 5 , 6) // Replace 5 with 6

    result 1 -> 2 -> 3 -> 4 -> 6 -> 6 ->7

Base code

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node *next;

    Node(int da = 0, Node *p = NULL) {
        this->data = da;
        this->next = p;
    }
};

class LinkedList {
private:
    Node *head, *tail;
    int position;
public:
    LinkedList() { head = tail = NULL; };

    ~LinkedList() {
        delete head;
        delete tail;
    };

    void print();
    void Insert(int da = 0);

}

void LinkedList::Insert(int da) {
    if (head == NULL) {
        head = tail = new Node(da);
        head->next = NULL;
        tail->next = NULL;
    } else {
        Node *p = new Node(da);
        tail->next = p;
        tail = p;
        tail->next = NULL;

}

}

int main() {
    cout << "Hello World!" << endl;
    LinkedList l1;
    l1.Insert(1);
    l1.Insert(2;
    l1.Insert(3);
    l1.Insert(4);
    l1.Insert(5);         l1.Insert(6);

l1.Insert(7);

    l1.print();

   l1.replaceNode( 5 , 6)

   l1.print();
    cout << "The End!" << endl;
    return 0;
}

    }

}

Answer 1

Solution: -

// program to replace two nodes of a linked list
#include <iostream>
using namespace std;
class Node { // Linked list node
public:
int data;
class Node* next;
Node(int val, Node* next) // Constructor
: data(val), next(next)
{
}
void printList() // Used to print linked list
{
Node* node = this;
while (node != NULL) {
cout <<"->";
cout << node->data;
node = node->next;
}
cout << endl;
}
};
void Insert(Node** head_ref, int new_data) // Insert a node beginning of Linked list
{
(*head_ref) = new Node(new_data, *head_ref);
}
void swap(Node*& a, Node*& b) // Used to swap a,b
{
Node* temp = a;
a = b;
b = temp;
}
void replaceNode(Node** head_ref, int x, int y) // replaceNode is used to repace two nodes
{
if (x == y) // x and y are same do nothing
return;
Node **a = NULL, **b = NULL;
while (*head_ref) { // Search for x and y and save pointer in a,b
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) { // Replace current pointer and next pointer of a,b
swap(*a, *b);
swap(((*a)->next), ((*b)->next));
}
}

int main()
{
Node* node= NULL;
Insert(&node, 7); // Linked list 1 -> 2 -> 3 -> 4 -> 5-> 6 ->7
Insert(&node, 6);
Insert(&node, 5);
Insert(&node, 4);
Insert(&node, 3);
Insert(&node, 2);
Insert(&node, 1);
cout << "Before calling replaceNode() Linked list is : ";
node->printList();
replaceNode(&node, 5, 6); // Replace 5 with 6
cout << "After   calling replaceNode() Linked list is : ";
node->printList();
}
Output: For the above program,

=========================================================
Comment if any query.