I just need help with the void switchSecondAndThird(const Node * s) Thanks! #inc
ID: 3838110 • Letter: I
Question
I just need help with the void switchSecondAndThird(const Node * s) Thanks!
#include <iostream>
using namespace::std;
struct Node
{
int data;
Node * next;
Node * prev;
};
void addFront(Node * & s, int value)
{
if ( s == NULL )
{
s = new Node;
s->data = value;
s->next = NULL;
s->prev = NULL;
return;
}
Node * p = new Node;
p->data = value;
p->prev = NULL; // prev is NULL for first node
s->prev = p; // old first node points backward to new first node
p->next = s; // new first node points forward to old first node
s = p; // s now points to new first node
}
void printForward(const Node * s)
{
const Node * walker = s;
while ( walker != NULL )
{
cout << walker->data << " ";
walker = walker->next;
}
cout << endl;
}
void deleteDoubleLinkedList(Node *s)
{
if ( s == NULL ) return; // 0 nodes
if ( s->next == NULL ) // 1 node
{
delete s;
return;
}
Node * prev = s;
Node * current = prev->next;
while ( current != NULL )
{
cout << "deleting " << prev-> data << endl;
delete prev;
prev = current;
current = current->next;
}
cout << "deleting " << prev-> data << endl;
delete prev;
cout << "All memory returned for double linked list starting at " << s << endl;
}
void deleteDoulbeLinkedListRecursive(Node * s) // write a recursive algorithm
{
/*if (s == nullptr)
{
cout << "Empty List" << endl;
}
if (s->next == NULL)
{
delete s;
return;
}
while (s != nullptr)
{
cout << "Deleting " << s->data << endl;
delete s;
deleteDoulbeLinkedListRecursive(s->next);
}
s = nullptr;
//delete s;*/
if (s == nullptr)
{
cout << "Empty List" << endl;
return;
}
Node *temp = s;
if (s->next == nullptr)
{
cout << "Deleting " << s->data << endl;
//s->next = nullptr;
delete s;
deleteDoulbeLinkedListRecursive(temp->next);
//s = s->next;
//delete s;
//deleteDoulbeLinkedListRecursive(s->next);
}
temp = nullptr;
}
int sumOfDataInNodes(const Node * s) // student writes this function
{
if(s == nullptr)
return 0;
return s->data + sumOfDataInNodes(s->next);
}
void printBackward(const Node * s) // student writes this function
{
if(s == nullptr)
cout << "" << endl;
const Node * walker = s;
while (walker->next != nullptr)
{
walker = walker->next;
}
cout << walker->data << " ";
while (walker->prev != nullptr)
{
cout << walker->prev->data << " ";
walker = walker->prev;
}
cout << endl;
delete walker;
walker = nullptr;
return;
}
void switchSecondAndThird(const Node * s) // assume at least 3 nodes Student writes this function
// MOVE POINTERS, DO NOT MOVE DATA
// CONSIDER A SPECIAL CASE OF EXACTLY 3 NODES, i.e., THERE IS NO 4TH NODE POINTING BACK TO THE THIRD NODE
{
}
void main()
{
Node * start = NULL;
for ( int i = 50; i >= 10; i-=10 )
{
addFront(start,i);
}
//cout <<"Start forward is ";
//printForward(start);
//cout <<"Start backward is ";
//printBackward(start);
cout << "The sum of the data is start is " << sumOfDataInNodes(start) << endl;
//switchSecondAndThird(start);
cout <<"Start forward after switching is ";
printForward(start);
cout <<"Start backward after switching is ";
printBackward(start);
deleteDoulbeLinkedListRecursive(start);
//printForward(start);
/*Node * special = NULL;
for ( int i = 130; i >= 110; i-=10 )
{
addFront(special,i);
}
cout <<"Special forward is ";
printForward(special);
cout <<"Special backward is ";
printBackward(special);
switchSecondAndThird(special);
cout <<"Special forward after switching is ";
printForward(special);
cout <<"Special backward after switching is ";
printBackward(special);
cout << "Return memory for Start" << endl;
deleteDoubleLinkedList(start);
*/
}
Explanation / Answer
Here is the code for the function only
-----------------------------------------------------------
void switchSecondAndThird(Node * s) // assume at least 3 nodes Student writes this function
// MOVE POINTERS, DO NOT MOVE DATA
// CONSIDER A SPECIAL CASE OF EXACTLY 3 NODES, i.e., THERE IS NO 4TH NODE POINTING BACK TO THE THIRD NODE
{
Node *temp = s->next; //assign second node to temp
s->next = temp->next; //initializing start->next to third node.
temp->next->prev = s; //set third-node->prev to start node
if (temp->next->next == NULL) //if 4th node is not there
{
temp->next = NULL; //set second-node->next to NULL
}
else
{
temp->next->next->prev = temp; //else set fourth-node->prev to second-node
temp->next = temp->next->next; //set second-node->next to forth -node
}
temp->prev = s->next; //set second-node->prev to third->node
s->next->next = temp; //set third-node->next to second node
}