Changing pointer passed to a function as argument

If a function in C/C++ takes a pointer argument and we try to change it (Not the value pointed to by pointer but the pointer itself). It should be done with caution to avoid undesired results …
Lets take an example of the function to insert an element in a linked list which is maintained in the sorted order. The structure of the Node is as shown below:

    struct Node
    {
        /* Keeping all public for simplicity reason, Not a good practice */
        public:
            int data;
            Node * link;
            Node(int value):data(value),  link(NULL) { }
            /* Good practice to initialize in the Member initialization list*/
    };

The insert function takes two arguments, The head of the list in which we want to insert and the value to be inserted. The below function is an INCORRECT IMPLEMENTATION of insert function.

    /* Function to insert a value in a sorted linked list.*/
    void  insert(Node *head, int value)
    {
        /* Creating new node with the value */
        Node* temp = new Node(value);
        if(head == NULL || head->data > value)
        {
            /* If no element in the list or the first element is larger than value */
            temp->link = head;
            /* Update the local variable ‘head' and not the actual argument */
            head = temp;
        }
        else
        {
            /* Loop to find the position to insert */
            while(head->link != NULL && head->link->data < value)
            {
                head = head->link;
            }
            /* inserting new node after head. */
            temp->link = head->link;
            head->link = temp;
        }
    }

If you have ever implemented linked list in C/C++ (on your own ) you may have found the problem in the above function. The above function does not ever update the pointer with which it is called, In fact it cannot update the actual argument because of the way argument is passed (i.e pass-by-value). Consider the below sequence of calls to this function:

    Node * list = NULL;
    list.insert(5);
    list.insert(7);
    list.insert(1);

We may expect variable list to point to a link list like below:

 
But Computers are not intelligent enough to interpret our expectations. They can only interpret our code. In the Function we are updating the head pointer which is a local variable to the function. This does not update the actual argument of the calling function, which is list.
So if we are attempting to modify the actual argument, which we do in two cases:

1. When the list is empty, then we create the first node and assign its address to the head.
2. If the element being inserted is the smallest in the list, then we insert it at the start of the list and update the head pointer.

Then our code will not behave in the desired way. In all other cases (where we are not modifying the head, the above function should works fine).
Just to reiterate, If list is pointing to a valid memory and head is changing the content of that memory, then the change would have been reflected in the *list (value pointed to by list). But, If we make change to head and expect the list variable to change itself (and not the value-at-list), then we need to do it differently. Because, like other variable, a pointer variable is also passed-by-value.
Below picture shows what happens when we change the value pointed to by a pointer in the called function.

And below is the picture showing what happens when we change the pointer itself.

Hence, we can change the value pointed to by a pointer inside the called function, but not the pointer itself. (At least, not the way we are doing it in the above example).
Next: Solution to the problem …