Reverse a Singly Linked List

In c++, For this lab you are required to write a member function for a list class which will effectively reverse the linked list. Please use function template provided to complete this lab.

Ex. If you list looks like this: 2 -> 15 -> 6 -> 1 Your function would alter the list to look like this: 1 -> 6 -> 15 -> 2

#include

using namespace std;

// Assume you have the following structures. Feel free to add extra helper

// functions if you find them necessary. Mark your additions via comments.

template

struct Node{

Node* next;

T data;

};

template

class LinkedList{

public:

LinkedList() : size(0), head(NULL) {}

void add(T data); // Adds to the front of the list

T& getElement(int pos); // Starts counting at 1, rather than 0

int getSize() { return size; }

bool isEmpty() { return size == 0; }

void display();

template

friend ostream& operator<<(ostream& out, const LinkedList& list);

bool operator==(LinkedList& rhs);

void reverse(); // Implement this function

private:

Node* head;

int size;

};

template

void LinkedList::reverse(){

// Implement this function

}

template

void LinkedList::add(T data){

Node* newNode = new Node();

newNode->data = data;

newNode->next = head;

head = newNode;

size++;

}

template

T& LinkedList::getElement(int pos){

if (pos < 1 || pos > size) throw - 1;

Node* curr = head;

for (int i = 1; i < pos; i++){

curr = curr->next;

}

return curr->data;

}

template

void LinkedList::display(){

Node* curr = head;

while (curr != NULL){

cout << curr->data << " -> ";

curr = curr->next;

}

cout << "NULL";

}

template

ostream& operator<<(ostream& out, const LinkedList& list){

Node* curr = list.head;

while (curr != NULL){

out << curr->data << " -> ";

curr = curr->next;

}

out << "NULL";

return out;

}

template

bool LinkedList::operator==(LinkedList& rhs){

if (size != rhs.size) return false;

Node * a = head;

Node * b = rhs.head;

while (a != NULL){

if (a->data != b->data) return false;

a = a->next;

b = b->next;

}

return true;

}

int main(){

// Your testing code goes here

return 0;

}