Link to home
Start Free TrialLog in
Avatar of Binnooh
BinnoohFlag for United States of America

asked on

Reverse function for linked list (Node) c++

here is the projects question
Write a void function that takes a linked list of integers and reverses the order of its nodes. The function will have one call-by-reference parameter that is a pointer to the head of the list. After the function is called, this pointer will point to the head of a linked list that has the same nodes as the original list, but in the reverse of the order they had in the original list. Note that your function will neither create nor destroy any nodes. It will simply rearrange nodes. Place your function in a suitable test program.

You will need to define a class intNode. Each node on the linked list will be an object of this class. You also need to (1) implement a function that inserts a node to the linked list at the front, (2) implement a function that traverses the linked list and print out the information on the list, and (3) implement a function that reverse the list. FInally, you are NOT ALLOWED to create a secondary list.
----

I have done the whole thing,
but i'm having little trouble in the reverse function!
how can i implement a (void) function that returns a reverse order of linked list?
(code is attached)

#include <iostream>
using namespace std; 
class IntNode{
public:
    IntNode();
    IntNode(int xData, IntNode *nextNode);
    
    int getData() const;
    IntNode * getNext() const;
    
    void setData( int Data );
    void setNext(IntNode * nextNode);
	IntNode* Reverse( IntNode *head );
	IntNode* travers (IntNode *head)
	
private:
    int Data; 
    IntNode *link; 
}; 
IntNode *insertNodeFront( IntNode *head, IntNode *newNode);  
IntNode *insertNodeEnd( IntNode *head, IntNode *newNode); 
void Print( IntNode *head );
void deleteLink( IntNode *head );
void Reverse(IntNode *head); 
IntNode::IntNode()
{
	Data = 0;
	link = NULL;
} 
IntNode::IntNode(int xData, IntNode *nextNode)
{
	Data = xData;
	link = nextNode;
} 
int IntNode::getData() const
{
	return Data; 
} 
IntNode* IntNode::getNext() const
{
	if (this == NULL ) 
		return NULL;
	return link;
} 
void IntNode::setData(int xData)
{
	Data = xData;
} 
void IntNode::setNext( IntNode *nextNode)
{
	(*this).link = nextNode;
} 
 
IntNode *insertNodeFront( IntNode *head, IntNode *newNode)
{
	newNode->setNext( head );
	return newNode; 
}  
IntNode *insertNodeEnd( IntNode *head, IntNode *newNode)
{
	IntNode *last=NULL;
	
	if ( head->getNext() == NULL )
		last = head;
	else{
		last = head->getNext();
		while ( last->getNext() != NULL )
			last = last->getNext();
	}
	last->setNext( newNode );
	return head; 
}  
void Print( IntNode *head )
{
	
	while (head != NULL)
	{
		cout << head->getData() << ' ';
		head = head->getNext();
	}
} 
IntNode* IntNode::travers (IntNode *head)
{
	head = link;
	while ( head.getNext () !=NULL)
		head = head.getNext ();
	
	return head;
}
/*
this is the reverse function!
it's suppose to change order of the liked list
*/  
void Reverse(IntNode *head) 
{
    IntNode firstNode = link;
	IntNode secondNode = // tail or last node ;
	int numberOfRun = // linke.Length / 2; 
	// Division will always be integer since the numberOfRun variable is an integer
	
	// ------------------------------------------------------------
	// Swap nodes objects
	// ------------------------------------------------------------
	
	IntNode temp; // This will be used in the swapping 2 objects
	for (int i=0; i < numberOfRun; i++)
	{
		// Swap the objects by using a 3rd temporary variable
		temp = firstNode;
		firstNode = secondNode;
		secondNode = temp;
		
		// Hop to the next node from the beginning and previous node from the end
		firstNode = firstNode.getNext();
		secondNode = secondNode.getNext();
	}
} 
void deleteLink( IntNode *head )
{
	IntNode *toDelete=NULL, *link=NULL;  
	
	toDelete = head;
	while ( toDelete!= NULL )
	{ 
		link = toDelete->getNext();
		delete toDelete;
		toDelete = NULL;
		toDelete = link;
	} 
} 
int main ()
{
    cout << "We are good " << endl;
    IntNode *head=NULL; 
    IntNode *newNode=NULL;
	
    head = new IntNode(4,NULL);
	
    newNode = new IntNode(5,NULL );
    head = insertNodeFront( head, newNode);
	
    newNode = new IntNode(2,NULL );
    head = insertNodeEnd( head, newNode);
    
    Print( head );
    Reverse( head );
	cout << "after reverse: \n";
    Print( head );
    return(0);
}

Open in new window

Avatar of Let_Me_Be
Let_Me_Be
Flag of United States of America image

> how can i implement a (void) function that returns a reverse order of linked list?

You should read more carefully. You are supposed to take the pointer using call-by-reference not call-by-value.
Avatar of Binnooh

ASKER

OK, i tried calling the function by reference (&)

but my problem is in implementing the function itself,
i tried to swap node and switch the  beginning to end (but that doesn't seem to work )

there must be another way to do it!!

ASKER CERTIFIED SOLUTION
Avatar of jhshukla
jhshukla
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of Binnooh

ASKER

Thank you, both jhshukla and Let_Me_Be

i really appreciate your comments!

 i figured that i'm retreating the pointers as values (not pointers)
and i made changes on the traverse function and called it (traverseList)

thank you to both of you!

P.S line 41 is completely correct, and it points automatically to the pointer (wouldn't work if you have multiple pointers)
((it works for me fine and it does its job!))
void traverseList(IntNode* head)
{
     int count = 0;
     IntNode* curr = NULL;
     curr = head;
     
     while(curr != NULL)
     {
          count++;
          cout << "Node " << count << ": " << curr->getNum() <<endl;
          curr = curr->getNext();
     }
} 
void reverseList(IntNode* head)
{
     IntNode *last = NULL, *prev = NULL, *next = NULL; //curr = current node to change address
     
     last = head;
     prev = head;
     next = head->getNext();
     //head = head->getNext();
     last->setNext(NULL);
     
     while(next != NULL)
     {
          head = next;
          next = head->getNext();
          head->setNext(prev);
          prev = head;
     }
     traverseList(head);
}

Open in new window

Avatar of Binnooh

ASKER

Good job experts