3 Replies - 1954 Views - Last Post: 11 April 2010 - 02:38 AM Rate Topic: -----

#1 GreenOrc  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 26
  • Joined: 28-February 10

What's wrong to my Reverse linked list function?

Posted 11 April 2010 - 12:04 AM

Hello expert programmers out there.

I have some trouble to understand how a "reverse link list" function work. I understand how pointers work, but the logic of reversing a linked list just drives me confused. I am working on a Node class for linked list. I got my print list function work but could not completely make the reverse list function work.

I am very appreciated any help there is.

Here's my source code:

Header file: Node.h
#ifndef NODE_H //infdef = If Not Defined
#define NODE_H
#include <cstdlib>
namespace NODE
{
	class Node
	{
	public:
		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;}
		//To retrieve the current data:
		value_type data() const {return data_field;}

		//Two slightly different member functions to retrieve the current link:
		const Node* link() const {return link_field;}
		Node* link() {return link_field;}
		
		//DESTRUCTOR:
		~Node();
		private:
			value_type data_field;
			Node* link_field;
	};
		//NON-MEMBER FUNCTIONS:
		void print_list (Node*);//print list
		Node* reverse_list(Node*);//reverse the list
}
#endif




Implementation file: Node.cpp
//File: Node.cpp
//CLASS IMPLEMENTATED: Node

#include <iostream>
#include <cstdlib>
#include "Node.h"
using namespace std;
namespace NODE
{
	//NON-MEMBER FUNCTIONS:
	//Print list
	void print_list (Node* prt)
	{
		for (; prt; prt = prt-> link())
			cout << prt->data() << " ";
	}

	//Reverse list
	Node* reverse_list(Node* head)
		/*I don't know the logic of this thing (I ONLY google this function on a website):
		Node* reverse_list(Node* head)
		{
			Node* newList = NULL;
			Node* current = head;
			while (current)
			{
				Node* next = current->next;
				current->next = newList;

				newList = current;
				current = next;
			}
			return newList;
		}*/
	//And then I create the version that match my Node class. 
	//I don't know what's wrong with my version of reverse list:
	{
		Node* newList = NULL;
		Node* current = head;
		while (current)
		{
			Node* next = current-> link();
			newList = current-> link();

			newList = current;
			current = next;
		}
		return newList;
	}
	//DESTRUCTOR:
	Node::~Node()
	{
	}
}



Demo file: NodeDemo.cpp
//File: NodeDemo.cpp
#include <iostream>
using namespace std;
#include "Node.h"
using namespace NODE;

int main ()
{
	Node a, b, c, d, e, f;

	Node* head = &a;
	
	a.set_data ('A');
	a.set_link (&B)/>;
	b.set_data ('B');
	b.set_link (&c);
	c.set_data ('C');
	c.set_link (&d);
	d.set_data ('D');
	d.set_link (&e);
	e.set_data ('E');
	e.set_link (&f);
	f.set_data ('F');
	f.set_link (NULL);

	print_list (head);//Print the list
	cout<<endl;
	head = reverse_list (head);//Reverse the list
	print_list (head);
	cout<<endl;
	

	system ("pause");
	return 0;
}



When I run it. It prints: "A B C D E F". Then it reverse the list, and print again but on "F". This where I stuck.

Is This A Good Question/Topic? 0
  • +

Replies To: What's wrong to my Reverse linked list function?

#2 n8wxs  Icon User is offline

  • --... ...-- -.. . -. ---.. .-- -..- ...
  • member icon

Reputation: 972
  • View blog
  • Posts: 3,878
  • Joined: 07-January 08

Re: What's wrong to my Reverse linked list function?

Posted 11 April 2010 - 12:50 AM

...
Node* reverse_list(Node* head)
	/*I don't know the logic of this thing (I ONLY google this function on a website):
	Node* reverse_list(Node* head)
	{
	Node* newList = NULL;
	Node* current = head;

	while (current)
	{
		Node* next = current->next;
		current->next = newList;

		newList = current;
		current = next;
	}
	return newList;
	}*/
	//And then I create the version that match my Node class. 
	//I don't know what's wrong with my version of reverse list:
{
	Node* newList = NULL;
	Node* current = head;

	while (current)
	{
		Node* next = current-> link();
		current-> set_link(newList);

		newList = current;
		current = next;
	}
	return newList;
}
...



...
print_list (head);//Print the list
cout<<endl;

head = reverse_list (head);//Reverse the list

print_list (head);//Print the list
...
cout<<endl;



Output:

Quote

A B C D E F
F E D C B A

Press any key to continue . . .

Was This Post Helpful? 1
  • +
  • -

#3 GreenOrc  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 26
  • Joined: 28-February 10

Re: What's wrong to my Reverse linked list function?

Posted 11 April 2010 - 01:10 AM

@n8wxs

Thank you sir for your great reply. It's working perfectly.

However I still don't understand what actually happen in the while loop, especially how the pointer of a node points to the reverse direction after the while loop.
Could you please clear my mind? See if my comments are correct!

//Node a, b, c, d, e , f which are mentioned below.
Node* reverse_list(Node* head)
{
	Node* newList = NULL;
        Node* current = head; // declare pointer current = head pointer

        while (current) //while current is not NULL do:
        {
		//declare pointer next = the pointer where the pointer of the
		//head node a points to. So next now points to b.
                Node* next = current-> link();
		//current node which is a. Set the pointer of a = newList.
                current-> set_link(newList);

                newList = current; //Now newList (pointer of a) = current = head.
                current = next; //Now current (head, newList) = next.
        }
        return newList; //Now a head pointer of node a.
	//This cycle will keep going until when? I cannot imagine. Can you help me?
	//I know f will become the head node. But I don't know how f.link() (pointer of f)
	// points to e; How e.link() points to d, ect... after the while loop?


This post has been edited by GreenOrc: 11 April 2010 - 01:55 AM

Was This Post Helpful? 0
  • +
  • -

#4 n8wxs  Icon User is offline

  • --... ...-- -.. . -. ---.. .-- -..- ...
  • member icon

Reputation: 972
  • View blog
  • Posts: 3,878
  • Joined: 07-January 08

Re: What's wrong to my Reverse linked list function?

Posted 11 April 2010 - 02:38 AM

Node* newList = NULL; // new list head
Node* current = head; // get current list: node a

while (current) // current != NULL
{
	// get next node in old list
	Node* next = current-> link();

	// point current to top of new list
	current-> set_link(newList);
	// and become head of that list
	newList = current;

	// next is top of old list: node b, c, d, e, f in turn
	current = next;
}


This post has been edited by n8wxs: 11 April 2010 - 02:45 AM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1