c++c++11pointerslinked-listnull-pointer

Why my head pointer is changing in linked list,even not passing it by reference?


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.

image of output


Solution

  • 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.