I created a linked list, and made a function reverseList which takes a pointer to head and return pointer to last node.
Node* reverseList(Node *head)
{
Node* curr=head;
Node* prev=NULL;
Node* ahead;
while(curr!=NULL)
{
ahead=curr->next;
curr->next=prev;
prev=curr;
curr=ahead;
}
return prev;
}
But in main when I am doing this
int main()
{
int n;///no of elements in list
cin>>n;
Node* head=NULL;
head=createList(head,n);///creating list(it is working properly)
printList(head);
cout<<endl;
Node* temp=reverseList(head);///reversing list and storing address of list in
//new node
printList(temp);///printing reversed list properly
cout<<endl;
printList(head);///while printing this it is printing only one elements,
//which implies head pointer changes but I don't know
///how
}
My head pointer changes, and it is printing only one value. I had pass my head pointer in reverseList by value. I am providing image of output.
Comments explain fine already, trying to illustrate to make it a little clearer:
1 > 2 > 3 > 4 > NULL
^
head
Now you reverse the list, resulting in:
4 > 3 > 2 > 1 > NULL
^ ^
temp head
As you never changed head, it still points to the same node as it pointed to before the list reversal, but after reversing the list, this node is now the last one.
Side note: Forgetting to re-assign is quite a common error, so it is a good idea to encapsulate the linked list in a separate class:
class LinkedList
{
Node* _head;
public:
class Node; // just as you have already
void reverse() // now a member function
{
//reverse as you did before
// encapsulating the assignment: (!)
_head = newHead;
}
Node* head() { return _head; }
};
LinkedList l;
// ...
Node* tmp = l.head();
l.reverse();
// tmp variable points to tail...
// expecting tmp pointing to head is still an error,
// and there is no way to prevent it
// BUT the correct head can always be re-acquired:
head = l.head();
Edit in response to comment:
If you want to create a new list, you will have to copy the nodes:
Node* createReversedList(Node* head)
{
Node* cur = NULL;
while(head)
{
Node* tmp = new Node(*head);
// (provided you have an appropriate copy constructor)
tmp->next = cur;
cur = tmp;
head = head->next;
}
return cur;
}
Note the new name, reverse rather implies modifying the original list as you did.