how to reverse a list

// I would like to add a new function to my class, "reverse" that would reverse the order of
// the list. I have added a prototype in the "public:" section of the code (see the comment
// with PROTOTYPE in it). Your task is to complete the implementation (see the comment with
// IMPLEMENTATION in it. See the main() function to see how the results should look

#include <iostream>
#include <cassert>
using namespace std;

class List
{
public:
// Constructs an empty list
List();

// Returns true if list is empty, false otherwise
bool empty();

// Inserts an integer item into the list AFTER the item in position 'pos'
// If pos = -1, insert the item at the head of the list.
void insert(int item, int pos);

// Remove an item from the list.
void remove(int pos);

// Get a copy of the indicated item from the list
int get(int pos);

// PROTOTYPE for reverse function
// It returns a new list whose values are in reverse order.
List reverse();

// Display the list in sequential order, with one space separating items.
void display();

private:
// This is private because no one needs to know how we implement the list
struct node
{
int data;
struct node *next;
};
typedef struct node Node;

Node* head;

// This private method will travers the list from the beginning to find the
// n-th item.
Node* find(int pos);
};

// Implementation of constructor
List::List()
{
head = 0;
}

// Implementation of empty function
bool List::empty()
{
return !head; // This is a power-programmer idiom for "return head == 0"
}

// Implementation of private find() function, used by several functions
List::Node* List::find(int pos)
{
if (pos < 0) return 0; // If the user is asking for position < 0, return null

Node* ptr = head;
while (pos-- && ptr) // While we are still in the list (ptr != 0)
ptr = ptr->next; // keep moving, while we haven't reached our desired position
return ptr; // Note that this returns null if the user requests a position too high
}


// Inserts an integer item into the list AFTER the item in position 'pos'
// If pos < 0,, insert the item at the head of the list.
// If pos > length of list, insert an end of list
void List::insert(int item, int pos)
{
// Here we prepare a new node to hold the data item
Node* node = new Node();
node->data = item;
if (pos < 0) // In this case we are inserting at the head of the list
{
node->next = head; // If the list was empty, this new node will be the end node, too.
head = node; // head now points to this node.
}
else
{
Node* ptr = find(pos); // Find the node to insert after (possibly the end node)
node->next = ptr->next; // Copy the previous's pointer to this node
ptr->next = node; // make the preview node point to this one.
}
}

// Remove an item from the list.
void List::remove(int pos)
{
if (pos < 0) return; // Do nothing if asking for item "left" of list
pos--; // Find the desired node, less one
if (pos == 0) // Removing the head; special case
{
Node* ptr = head; // Get a pointer to the head so we can delete it later
head = head->next; // Make the next node the new head;
delete ptr; // and delete the old head.
}
else
{
Node* ptr = find(pos - 1); // Find the node right before the target
Node* tgt = ptr->next; // Get a pointer to the target node
ptr->next = tgt->next; // Fix up the links
delete tgt; // And delete the target;
}
}

// Get a copy of the indicated item from the list
int List::get(int pos)
{
Node* ptr = find(pos); // Find the desired node
assert(ptr);
return ptr->data;
}

// This IMPLEMENTATION allocates a list called "result", puts items
// into it in reverse order from the bound object's data, and returns
// result.
List List::reverse()
{
List result;

//node* temp;
//node* tobe = NULL;
//while(temp != null)
//{
//temp = result->next;
//result->next = tobe;
//tobe = result;
//now = temp;
// this code does not work just an example of what I tried
}

return result;
}


// Display the list in sequential order, with one space separating items.
void List::display()
{
Node* ptr = head;
while (ptr)
{
cout << ptr->data << endl;
ptr = ptr->next;
}
cout << endl;
}

int main()
{
// DO NOT TOUCH THIS CODE. YOUR WORK GOES IN THE "reverse" function.

// Definition of raw data
int data[] = {1, 3, 2, 5, 9};
int length = sizeof(data)/sizeof(data[0]);

// Build and display original list
List orig;
for (int i = 0; i < length; i++)
orig.insert(data[i], -1); // Insert at head
orig.display();
// Should display
// 9
// 5
// 3
// 2
// 1

// Now make and display a reversed list
List reverse = orig.reverse();
reverse.display();
// Should display
// 1
// 2
// 3
// 5
// 9

return 0;
}



I cant seem to get the right function to put into reverse I have tried everything Im not sure where to start!
Last edited on
The keyword to search with is "recursion".
This is trivial to solve without recursion. Begin by describing the algorithm you would use to build a list from the current one in reverse order.
My bad. It is indeed trivial, and a recursive solution would not fit here.

May I ask what level of education uses assignments of this type?
Without testing


1
2
3
4
5
6
7
8
9
10
11
12
13
14
List List::reverse()
{
   List reversed;

   for ( Node *next = head; next; next = next->next )
   {
      Node *n = new Node();
      n->data = next->data;
      n->next = reversed.head;
      reversed.head = n;
   }

   return ( reversed );
}
Topic archived. No new replies allowed.