Question

# Exercise 1 In this exercise, you will add a method swapNodes to SinglyLinkedList class. This method...

Exercise 1

In this exercise, you will add a method swapNodes to SinglyLinkedList class. This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same node, etc. Write the main method to test the swapNodes method. Hint: You may need to traverse the list.

Exercise 2

In this exercise, you will use the DoublyLinkedList implementation of the textbook. Write a method for concatenating two doubly linked lists L and M, with header and trailer sentinel nodes, into a single list L′. Write a main method to test the new method. Hint: Connect the end of L into the beginning of M.

IMPLEMENTATION IN C++

Source Code:

#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *next;
};
void insert() // This method insert node at the beginning
{
int new_data;
cout<<"\n Enter new Node's Data:";
cin>>new_data;
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
}
void display() {
struct Node* ptr;
while (ptr != NULL) {
cout<< ptr->data <<"-->";
ptr = ptr->next;
}
}

{
int x,y;
cout<<"Enter the elements you want to swap:";
cin>>x>>y;
// Nothing to do if x and y are same
if (x == y) return;

// Search for x (keep track of prevX and CurrX
Node *prevX = NULL, *currX = *head_ref;
while (currX && currX->data != x)
{
prevX = currX;
currX = currX->next;
}

// Search for y (keep track of prevY and CurrY
Node *prevY = NULL, *currY = *head_ref;
while (currY && currY->data != y)
{
prevY = currY;
currY = currY->next;
}

// If either x or y is not present, nothing to do
if (currX == NULL || currY == NULL)
return;

if (prevX != NULL)
prevX->next = currY;
else // Else make y as new head

if (prevY != NULL)
prevY->next = currX;
else // Else make x as new head

// Swap next pointers
Node *temp = currY->next;
currY->next = currX->next;
currX->next = temp;
cout<<"\nSwapping Done";
}
int main() {
while(1)
{
int ch;
cin>>ch;
switch(ch)
{
case 1:insert();
break;
case 2:display();
break;
break;
case 4: exit(0);
default:cout<<"Invalid choice";
break;
}

}
}

Output:

2. Swap the nodes

Source Code:

#include <iostream>
using namespace std;
struct node {
int data;
struct node *prev;
struct node *next;
};

struct node *list = NULL;
struct node *list_last = NULL;

struct node *even = NULL;
struct node *even_last = NULL;

struct node *odd = NULL;
struct node *odd_last = NULL;

struct node *current = NULL;

void insert(int data) {
// Allocate memory for new node;
struct node *link = (struct node*) malloc(sizeof(struct node));

// If head is empty, create new list
if(data%2 == 0) {
if(even == NULL) {
return;
} else {
current = even;

while(current->next != NULL)
current = current->next;

// Insert link at the end of the list
}
} else {
if(odd == NULL) {
return;
} else {
current = odd;

while(current->next!=NULL)
current = current->next;

// Insert link at the end of the list
}
}
}

//display the list

cout<<"\n[last] <--->";
//start from the beginning
while(ptr != NULL) {
cout<<" <--->"<<ptr->data;
ptr = ptr->prev;
}

}

//display the list

//start from the beginning
while(ptr != NULL) {
cout<<" <--->"<<ptr->data;
ptr = ptr->next;
}

cout<<" [last]\n";
}

void combine() {

list = even;

}

// assign link_last to last node of new list

}

}

int main() {
int i;

for(i = 1; i <= 10; i++)
insert(i);

cout<<"Even : ";
printList(even);

cout<<"Even (R): ";
print_backward(even_last);

cout<<"Odd : ";
printList(odd);

cout<<"Odd (R) : ";
print_backward(odd_last);

combine();

cout<<"Combined List :\n";
printList(list);

cout<<"Combined List (R):\n";
print_backward(list_last);

return 0;
}

OUTPUT:

Even means list contains only even nodes

Odd means list contains only odd nodes.

#### Earn Coins

Coins can be redeemed for fabulous gifts.