#include <iostream>
#include "node1.h"
#include <cassert>
#include <cstdlib>
using namespace std;
using namespace main_savitch_5;
 
 
void print_list( node* head_ptr);
node* reverse_list(node* head_ptr);
 
void main()
{
	node* head_ptr;
 
	list_head_insert(head_ptr, 'F');
	list_head_insert(head_ptr, 'E');
	list_head_insert(head_ptr, 'D');
	list_head_insert(head_ptr, 'C');
	list_head_insert(head_ptr, 'B');
	list_head_insert(head_ptr, 'A');
 
	print_list(head_ptr);
	cout << endl;
	reverse_list(head_ptr);
	print_list(head_ptr);
	return;
}
 
void print_list(node* ptr)
{
	for (; ptr; ptr = ptr->link())
		cout << ptr->data() << " ";
	cout << endl;
	return;
}
 
 
node* reverse_list(node* head_ptr)
{
	cout << "Reversed..." << endl;
	node* result_ptr = NULL;
	node* curr_ptr = NULL;
	while (head_ptr)
	{
		curr_ptr = head_ptr;
		head_ptr = head_ptr->link( );
		curr_ptr->set_link(result_ptr);
		result_ptr = curr_ptr;
	}
	return result_ptr;
	//node* buffer1;
	//node* buffer2;
	//int i = 5;
	//buffer2 = ptr->info;
	//for (buffer1 = ptr->info; ptr; ptr = ptr->next)
	//{
	//	buffer2 = 
 
	//}
	//for (; ptr; ptr = ptr->next)
	//cout << ptr->info << " ";
}

// FILE: node1.cxx
// IMPLEMENTS: The functions of the node class and the
// linked list toolkit (see node1.h for documentation).
// INVARIANT for the node class:
//   The data of a node is stored in data_field, and the link in link_field.
 
#include "node1.h"
#include <cassert>    // Provides assert
#include <cstdlib>    // Provides NULL and size_t
using namespace std;
 
namespace main_savitch_5
{
    size_t list_length(const node* head_ptr)
    // Library facilities used: cstdlib
    {
	const node *cursor;
	size_t answer;
 
	answer = 0;
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    ++answer;
 
	return answer;
    }
 
    void list_head_insert(node*& head_ptr, const node::value_type& entry)
    {
	head_ptr = new node(entry, head_ptr);
    }
 
    void list_insert(node* previous_ptr, const node::value_type& entry) 
    {
	node *insert_ptr;
 
	insert_ptr = new node(entry, previous_ptr->link( ));
	previous_ptr->set_link(insert_ptr);
    }
 
    node* list_search(node* head_ptr, const node::value_type& target) 
    // Library facilities used: cstdlib
    {
	node *cursor;
 
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    if (target == cursor->data( ))
		return cursor;
	return NULL;
    }
 
    const node* list_search(const node* head_ptr, const node::value_type& target) 
    // Library facilities used: cstdlib
    {
	const node *cursor;
 
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    if (target == cursor->data( ))
		return cursor;
	return NULL;
    }
 
    node* list_locate(node* head_ptr, size_t position) 
    // Library facilities used: cassert, cstdlib
    {
	node *cursor;
	size_t i;
 
	assert (0 < position);
	cursor = head_ptr;
	for (i = 1; (i < position) && (cursor != NULL); i++)
	    cursor = cursor->link( );
	return cursor;
    }
 
    const node* list_locate(const node* head_ptr, size_t position) 
    // Library facilities used: cassert, cstdlib
    {
	const node *cursor;
	size_t i;
 
	assert (0 < position);
	cursor = head_ptr;
	for (i = 1; (i < position) && (cursor != NULL); i++)
	    cursor = cursor->link( );
	return cursor;
    }
 
    void list_head_remove(node*& head_ptr)
    {
	node *remove_ptr;
 
	remove_ptr = head_ptr;
	head_ptr = head_ptr->link( );
	delete remove_ptr;
    }
 
    void list_remove(node* previous_ptr)
    {
	node *remove_ptr;
 
	remove_ptr = previous_ptr->link( );
	previous_ptr->set_link( remove_ptr->link( ) );
	delete remove_ptr;
    }
 
    void list_clear(node*& head_ptr)
    // Library facilities used: cstdlib
    {
	while (head_ptr != NULL)
	    list_head_remove(head_ptr);
    }
 
    void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) 
    // Library facilities used: cstdlib
    {
	head_ptr = NULL;
	tail_ptr = NULL;
 
	// Handle the case of the empty list.
	if (source_ptr == NULL)
	    return;
 
	// Make the head node for the newly created list, and put data in it.
	list_head_insert(head_ptr, source_ptr->data( ));
	tail_ptr = head_ptr;
 
	// Copy the rest of the nodes one at a time, adding at the tail of new list.
	source_ptr = source_ptr->link( ); 
	while (source_ptr != NULL)
	{
	    list_insert(tail_ptr, source_ptr->data( ));
	    tail_ptr = tail_ptr->link( );
	    source_ptr = source_ptr->link( );
	}
    }
 
}

// FILE: node1.h
// PROVIDES: A class for a node in a linked list, and list manipulation
// functions, all within the namespace main_savitch_5
//
// TYPEDEF for the node class:
//     Each node of the list contains a piece of data and a pointer to the
//     next node. The type of the data is defined as node::value_type in a
//     typedef statement. The value_type may be any
//     of the built-in C++ classes (int, char, ...) or a class with a copy
//     constructor, an assignment operator, and a test for equality (x == y).
//
// CONSTRUCTOR for the node class:
//   node(
//     const value_type& init_data = value_type(),
//     node* init_link = NULL
//   )
//     Postcondition: The node contains the specified data and link.
//     NOTE: The default value for the init_data is obtained from the default
//     constructor of the value_type. In the ANSI/ISO standard, this notation
//     is also allowed for the built-in types, providing a default value of
//     zero. The init_link has a default value of NULL.
//
// NOTE:
//   Some of the functions have a return value which is a pointer to a node.
//   Each of these  functions comes in two versions: a non-const version (where
//   the return value is node*) and a const version (where the return value
//   is const node*). 
// EXAMPLES:
//    const node *c;
//    c->link( ) activates the const version of link
//    list_search(c,... calls the const version of list_search
//    node *p;
//    p->link( ) activates the non-const version of link
//    list_search(p,... calls the non-const version of list_search
//
// MEMBER FUNCTIONS for the node class:
//   void set_data(const value_type& new_data)
//     Postcondition: The node now contains the specified new data.
//   
//   void set_link(node* new_link)
//     Postcondition: The node now contains the specified new link.
//
//   value_type data( ) const
//     Postcondition: The return value is the data from this node.
//
//   const node* link( ) const <----- const version
//   node* link( ) <----------------- non-const version
//   See the note (above) about the const version and non-const versions:
//     Postcondition: The return value is the link from this node.
//   
// FUNCTIONS in the linked list toolkit:
//   size_t list_length(const node* head_ptr)
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: The value returned is the number of nodes in the linked
//     list.
//
//   void list_head_insert(node*& head_ptr, const node::value_type& entry) 
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: A new node containing the given entry has been added at
//     the head of the linked list; head_ptr now points to the head of the new,
//     longer linked list.
//
//   void list_insert(node* previous_ptr, const node::value_type& entry) 
//     Precondition: previous_ptr points to a node in a linked list.
//     Postcondition: A new node containing the given entry has been added
//     after the node that previous_ptr points to.
//
//   const node* list_search(const node* head_ptr, const node::value_type& target) 
//   node* list_search(node* head_ptr, const node::value_type& target) 
//   See the note (above) about the const version and non-const versions:
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: The pointer returned points to the first node containing
//     the specified target in its data member. If there is no such node, the
//     null pointer is returned.
//
//   const node* list_locate(const node* head_ptr, size_t position) 
//   node* list_locate(node* head_ptr, size_t position) 
//   See the note (above) about the const version and non-const versions:
//     Precondition: head_ptr is the head pointer of a linked list, and
//     position > 0.
//     Postcondition: The pointer returned points to the node at the specified
//     position in the list. (The head node is position 1, the next node is
//     position 2, and so on). If there is no such position, then the null
//     pointer is returned.
//
//   void list_head_remove(node*& head_ptr) 
//     Precondition: head_ptr is the head pointer of a linked list, with at
//     least one node.
//     Postcondition: The head node has been removed and returned to the heap;
//     head_ptr is now the head pointer of the new, shorter linked list.
//
//   void list_remove(node* previous_ptr) 
//     Precondition: previous_ptr points to a node in a linked list, and this
//     is not the tail node of the list.
//     Postcondition: The node after previous_ptr has been removed from the
//     linked list.
//
//   void list_clear(node*& head_ptr) 
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: All nodes of the list have been returned to the heap,
//     and the head_ptr is now NULL.
//
//   void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) 
//     Precondition: source_ptr is the head pointer of a linked list.
//     Postcondition: head_ptr and tail_ptr are the head and tail pointers for
//     a new list that contains the same items as the list pointed to by
//     source_ptr. The original list is unaltered.
//  void list_piece(
//    const node* start_ptr, const node* end_ptr, 
//    node*& head_ptr, node*& tail_ptr
//  )
//    Precondition: start_ptr and end_ptr are pointers to nodes on the same
//    linked list, with the start_ptr node at or before the end_ptr node
//    Postcondition: head_ptr and tail_ptr are the head and tail pointers for a
//    new list that contains the items from start_ptr up to but not including 
//    end_ptr.  The end_ptr may also be NULL, in which case the new list 
//    contains elements from start_ptr to the end of the list.
//
// DYNAMIC MEMORY usage by the toolkit: 
//   If there is insufficient dynamic memory, then the following functions throw
//   bad_alloc: the constructor, list_head_insert, list_insert, list_copy,
//   list_piece.
#include <iostream>
#ifndef MAIN_SAVITCH_NODE1_H  
#define MAIN_SAVITCH_NODE1_H
#include <cstdlib> // Provides size_t and NULL
 
namespace main_savitch_5
{
    class node
    {
    public:
	// TYPEDEF
	typedef char value_type;
 
	// CONSTRUCTOR
	node(
	    const value_type& init_data = value_type( ),
	    node* init_link = NULL
	)
	{ data_field = init_data; link_field = init_link; }
 
	// Member functions to set the data and link fields:
    	void set_data(const value_type& new_data) { data_field = new_data; }
    	void set_link(node* new_link)             { link_field = new_link; }
 
	// Constant member function to retrieve the current data:
	value_type data( ) const { return data_field; }
 
	// Two slightly different member functions to retreive
	// the current link:
	const node* link( ) const { return link_field; }
    	node* link( )             { return link_field; }
 
    private:
	value_type data_field;
	node* link_field;
    };
 
    // FUNCTIONS for the linked list toolkit
    size_t list_length(const node* head_ptr);
    void list_head_insert(node*& head_ptr, const node::value_type& entry); 
    void list_insert(node* previous_ptr, const node::value_type& entry);  
    node* list_search(node* head_ptr, const node::value_type& target);
    const node* list_search
	(const node* head_ptr, const node::value_type& target);
    node* list_locate(node* head_ptr, size_t position);
    const node* list_locate(const node* head_ptr, size_t position);
    void list_head_remove(node*& head_ptr);
    void list_remove(node* previous_ptr);
    void list_clear(node*& head_ptr);
    void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);
}
 
#endif

node* reverse_list(node* head_ptr){	
               cout << "Reversed..." << endl;
 	node* result_ptr = NULL;
	node* curr_ptr = NULL;
	while (head_ptr)
	{
		curr_ptr = head_ptr;
		head_ptr = head_ptr->link( );
		curr_ptr->set_link(result_ptr);
		result_ptr = curr_ptr;
	}
	return result_ptr;
}

void Reverse (Link* head)
{
	//checking preconditions.
	if (!head && !head->next)
	          return;
                //here we are sure that second node exists.
	Link* temp = head->next; // holding 2nd node reference.
                Link* iter = temp->next; // hold the reference of 3rd Node OR NULL.
	head->next = 0;  // setting the first Node next = 0; (why? think)
	while (temp)    // traversing from 2nd node to the end.
	{
		iter = temp->next;  // saving the 3rd Node.
		temp->next = head; // reversing the 2nd to point to first.
		head = temp;     // incrementing head.
		temp = iter;      // incrementing 2nd to 3rd saved abov.
	}
}