Question

The file supplied.o contains code that can build, display, and destroy a
linear linked list (singly-linked).

For this lab, you will need to write the following two functions in list.cpp,
and add function prototypes for them to list.h. The provided main.cpp has
calls to each of these functions commented out. As you write the functions,
uncomment them from main.cpp.

void reverse(node * head, node *& newHead)

Recursively make a revserse copy of the source list with head where
newhead is the head of the destination list.

void removeLast(node *& head)

Recursively the last node from this list.

You must use the functions with these exact function prototypes. Use the
supplied makefile for the project to build it. Please don't forget the
supplied.o when generating the executable.

Run your program in valgrind and make sure there are no memory errors or
memory leaks. Assuming the executable file is named app

valgrind --tool=memcheck --leak-check=full ./app

list.cpp

#include <iostream>
#include "list.h"

--------------------------------------------

list.h

#include <iostream>
#include <cstring>
#include <cctype>

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

/* These functions are already written and can be called to test out your code */
void build(node * & head); //supplied
void display(node * head); //supplied
void destroy(node * &head); //supplied

//Write your function prototype here:

------------------------------------------------

main.cpp

#include "list.h"
using namespace std;

int main()
{
node * head = NULL;
node * newHead = NULL;

cout << "----------------------------------------------------------------------" << endl;
cout << "Creating the initial list." << endl;
build(head);
display(head);

cout << "----------------------------------------------------------------------" << endl;
cout << "Reversing the list.";
// reverse(head,newHead);
display(newHead);
destroy(newHead);

cout << "----------------------------------------------------------------------" << endl;
cout << "Removing the last element.";
// removeLast(head);
display(head);
destroy(head);

return 0;
}

Answer 1

main.cpp file

#include "list.h"

using namespace std;

int main()
{
        node * head = NULL;
        node * newHead = NULL;

        cout << "----------------------------------------------------------------------" << endl;
        cout << "Creating the initial list." << endl;
        build(head);
        display(head);

        cout << "----------------------------------------------------------------------" << endl;
        cout << "Reversing the list.";
reverse(head,newHead);
        display(newHead);
        destroy(newHead);

        cout << "----------------------------------------------------------------------" << endl;
        cout << "Removing the last element.";
removeLast(head);
        display(head);
        destroy(head);


        return 0;
}

list.h

#include <iostream>
#include <cstring>
#include <cctype>


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

/* These functions are already written and can be called to test out your code */
void build(node * & head); //supplied
void display(node * head); //supplied
void destroy(node * &head); //supplied

//Write your function prototype here:
void reverse(node* &head,node* &newHead);
void removeLast(node* &head);
//------------------------------------------------

list.cpp

#include <iostream>
#include "list.h"


void reverse(node* &head, node* &newHead)
{
    /* last node, fix the head */
    if (head == NULL || head->next == NULL) {
        newHead = head;
        return;
    }
    reverse(head->next, newHead);
    head->next->next = head;
    head->next = NULL;
}


void removeLast(struct node* &head){
    
    if(head==NULL){
        return;
    }
    if(head->next==NULL){
      delete head;
      head=NULL;
      return;
    }
    if(head->next->next==NULL){
      delete head->next;
      head->next=NULL;
      return;
    }
    removeLast(head->next);
}

in reverse function:

• recursively call for next node till we reach the last node i.e. node==null
• when last node is reached then start reversing i.e. node->next->next=node

in removeLast function:

• traverse till last node recursively
• make cases i.e. node==null or node->next==null or node->next->next ==null
• remove last node

if code snippet is not well aligned please comment there is some problem with code editor i will paste as plane text then.