Question

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.

Answer 1

IMPLEMENTATION IN C++

Answer 1:

Source Code:

#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* head = NULL;
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;
new_node->next = head;
head = new_node;
}
void display() {
struct Node* ptr;
ptr = head;
while (ptr != NULL) {
cout<< ptr->data <<"-->";
ptr = ptr->next;
}
}

void swapNodes(Node **head_ref)
{
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 x is not head of linked list
if (prevX != NULL)
prevX->next = currY;
else // Else make y as new head
*head_ref = currY;
  
// If y is not head of linked list
if (prevY != NULL)
prevY->next = currX;
else // Else make x as new head
*head_ref = currX;
  
// Swap next pointers
Node *temp = currY->next;
currY->next = currX->next;
currX->next = temp;
cout<<"\nSwapping Done";
}
int main() {
while(1)
{
cout<<"\n1.Insert\n2.Display\n3.Swap\n4.Exit\nEnter your choice:";
int ch;
cin>>ch;
switch(ch)
{
case 1:insert();
break;
case 2:display();
break;
case 3:swapNodes(&head);
break;
case 4: exit(0);
default:cout<<"Invalid choice";
break;
}

}
}

Output:

1.Create and display linked list

2. Swap the nodes

Answer 2:

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;

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

link->data = data;
link->prev = NULL;
link->next = NULL;

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

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

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

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

// Insert link at the end of the list
current->next = link;
odd_last = link;
link->prev = current;
}
}
}

//display the list
void print_backward(struct node *head) {
struct node *ptr = head;

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

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

//display the list
void printList(struct node *head) {
struct node *ptr = head;

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

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

void combine() {
struct node *link;

list = even;
link = list;

while(link->next!= NULL) {
link = link->next;
}

link->next = odd;
odd->prev = link;

// assign link_last to last node of new list

while(link->next!= NULL) {
link = link->next;
}

list_last = link;
}

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.