Linked list head pointer not getting updated when called by reference

Question

I have written two functions to insert nodes in a Linked List. While one function (insertNth) updates the head pointer, the second one (sortedInsert) does not update the head pointer across function calls. The push function is taking a reference to the head pointer.

struct node
{
    int data;
    node *next;
};

void printList(node *head)
{
    node *current = head;

    while(current!=NULL)
    {
        cout<<current->data<<" ";
        current = current->next;
    }

}

void push(node* &head, int data)
{
    node *newNode = new node();

    newNode->data = data;
    newNode->next = head;
    head = newNode;
}

void insertNth(node *&head, int index, int val)
{
    node *current = head;

    int cnt = 0;

    while(current!=NULL)
    {
        if(cnt == index)
        {
            if(cnt==0)
            {
                push(head, val);
            }
            else
            {
                push(current->next, val);
            }
        }
        current=current->next;
        cnt++;
    }
}

void sortedInsert(node *head, int val)
{
    node *current = head;

    if(head != NULL && val < head->data)
    {
        node *newNode = new node();

        push(head,val);

        return;
    }

    while(current!=NULL)
    {
        if(current->data < val && current->next->data > val)
        {
            push(current->next, val);
            return;

        }
        current = current->next;
    }
}

int main()
{
    node *head;

    push(head, 3);
    cout<<"\n";
    printList(head);

    cout<<"\nInsertNth: ";
    insertNth(head,0, 2);
    printList(head);

    cout<<"\nsortedInsert: ";
    sortedInsert(head, 1);
    printList(head);

    return 0;
}

I'm getting following as output:

3 
InsertNth: 2 3 
sortedInsert: 2 3 

Why is the third line not printing 1 2 3?

// Update //

The correct SortedInsert is as follows:

void sortedInsert(node *&head, node *newNode)
{
    node *current = head;

    if(head == NULL || newNode->data < head->data)
    {

        newNode->next = head;
        head = newNode;

        return;
    }

    while(current!=NULL && current->next != NULL)
    {
        if(current->data < newNode->data && current->next->data > newNode->data)
        {

            newNode->next = current->next;
            current->next = newNode;

            return;

        }

        current = current->next;
    }
    if(current->next == NULL)
    {
        current->next = newNode;
        newNode->next = NULL;
    }
}

Answer 1

A sample was requested. Note that I did it as a template, but you could skip the template business and instead of a T* you can use struct node *. It's not general purpose, but might be easier to understand.

template <class T>
class MyLinkedList {
    class Entry {
    public:
        Entry * previous;
        Entry * next;
        T * node;
    }

    Entry * head;
    Entry * tail;

    void push(T * nodeToPush) { pushBefore(head, nodeToPush); }
    void insertNth(int whereToInsert, T * nodeToInsert) {
         ... find the nth Entry pointer
         pushBefore(head, nodeToPush);
    }

private:
    void pushBefore(Entry *entry, T * nodeToPush) {
        Entry *newEntry = new Entry();
        newEntry->node = nodeToPush;
        if (entry != NULL) {
            newEntry->previous = entry->previous;
        }
        newEntry->next = entry;
        entry->previous = newEntry;
        if (head == entry) {
            head = newEntry;
        }
        if (tail == NULL) {
            tail = newEntry;
        }
    }

    // Other methods as necessary, such as append, etc.
}

Other than passing in a pointer to the objects you're inserting into your linked list, at no point do you have to pass pointers around in a fashion where your methods are also performing side effects on those pointer. The class should know how to manage a class, and no weird passing of variables all over.

Performing side effects on your arguments should be done with GREAT caution. If you're passing an object to a method, then it's fair to manipulate the object. But I really don't like passing pointers and having methods modify the pointers themselves.

That IS going to lead to (at best) confusion.

Note: I did NOT test this code. It might not quite be perfect.