Recursively insert a node in an ordered Linked List I've written this and it works great. Is there any shorter or simpler way to achieve the same result without distinguish between cases?

Node* recursive_ordered_insert(Node* head, int val)
{
    //special case: first elem is null
    if (!head)
    {
        head = create_node(val);

        return head;
    }

    //special case 2: end of list
    if (!head-&gt;next)
    {
        head-&gt;next = create_node(val);

        return head-&gt;next;
    }

    //base case
    if (head-&gt;next &amp;&amp; head-&gt;next-&gt;data &gt; val)
    {
        Node* newNode = create_node(val);
        newNode-&gt;next = head-&gt;next;

        head-&gt;next = newNode;

        return newNode;
    }

    return recursive_ordered_insert(head-&gt;next, val);
}
The assumptions your code makes are... odd. Why do you have to use recursion. In reality, your code will overflow the stack for long lists, unless you ramp up the compiler optimization, and your compiler performs tail-call optimization on the recursion.

So, yes, you can do a recursive insert, and, assuming this is some sort of educational process, your implementation appears to be reasonable, with some caveats:


I don't like the "create if the list does not exist" logic in the first block. Using the head as an "output-parameter" is ugly. head should not be modified. The new head is returned anyway. The calling code should be able to tell if the head is null before it calls the insert method, and instead call a 'create' method of some sort. Additionally, that check is only ever needed once for the entire list, so it is a waste of time to check it for each level of recursion.
you cannot insert at the beginning of the list. If you are intending to insert the values {4, 3, 2, 1} and your first node starts as 4 at the 'head', well, you can't insert before that..... Your code requires that the first node is always the minimum value in order for the sort-order to be maintained.


Bottom line, is your code only works for limited use-cases.

I would much rather your code had a 'sentinel' head node, which was never null, and then your actual data follows from that head position. That would reduce your code, and make the insertion process simpler, and also fix both issues above. Note that the 'head' node would be kept as part of the class fields somewhere, not passed in as an argument to the (recursive) method... in fact, the method should not be recursive