CODEWITHSUNDEEP
c++c++11pointerslinked-listnull-pointer
Suhail Akhtar
Suhail Akhtar

Reputation: 629

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

Upvotes: -3

Views: 2695

Answers (2)

Aconcagua
Aconcagua

Reputation: 25536

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.

Upvotes: 4

Susmit Agrawal
Susmit Agrawal

Reputation: 3764

To create a new Linked List, you need to create a new variable of Node, and perform operations on that variable.

So, the code would be something like:

Node* reverseList(Node *head)
{
    Node* newRootPtr = new Node(); //Pointer to the new root. This will be returned to the calling function.

    newRootPtr->next = NULL;        //In the reversed list, the original head will be the last node.

    Node* curr=head;                //For iterations

    while(curr->next!=NULL)         //For every node, until the last node. Note that here, we need to stop at the last node, which will become the first node of the new List.
    {
        Node ahead=*(curr->next);   //Create a new Node equal to the next node of the original list.
        Node* aheadPtr = &ahead;        //Pointer to the new node
        aheadPtr->next = newRootPtr;    //Point the new node to the previous node of the new list
        newRootPtr = aheadPtr;          //update root node
        curr=curr->next;
    }

    return newRootPtr;
}

Upvotes: 0

Related Questions