Singly-Linked List In-Place Reversal

Question

I've created a function in C to reverse a singly-linked list in place:

typedef struct n {
    int key;
    struct n* next;
} node;

node* inplaceReverse(node* head, int index) {
    if(!head || !head->next) {
        /* Indication of last node (or empty list). This will be recursively returned to become the new head pointer of the reveresed list. */
        return head;
    }else {
        /* Reverse the list after head and store its return in tmp. */
        node* newhead = inplaceReverse(head->next,index+1);
        /* Make the next node's next point to head. */
        head->next->next = head;
        /* If head was the first node, make its next NULL. */
        if(!index) head->next = NULL;
        return newhead;
    }
}

It works but one thing that bothered me is that I needed to create an additional argument for the actual function (int index). This is to indicate the original head of the list so I know which one to set to NULL after the reverse. It feels like there's an obvious and better way to do this but I'm not sure.

Other suggestions for optimization and improvements are also welcomed.

Answer 1

My primary concern with this implementation is the fact that it is recursive and thus the amount of stack that you are consuming is directly proportional to the length of the linked list. If the linked list is something like 10 nodes long, you are likely going to be fine. However, if it is 1,000,000 nodes long then that is something that you can expect to blow the stack.

I would recommend rewriting the algorithm to not use recursion. This can be done in the following manner.

node = list->head;
if (node is NULL) then there is nothing to do

for (next = node->next; next != NULL; next = node->next) {
    remove 'next' from the list

    /*
     * the act of removing 'next' from the list will automatically
     * update node->next.  Note that 'node' never changes.
     */

    add 'next' to the head of the list
}

Hope this helps.