how to reverse a list

[jjaysteez]

// 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!

[keskiverto]

The keyword to search with is "recursion".

[cire]

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.

[keskiverto]

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?

[vlad from moscow]

Without testing

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 );
}