Auxiliary space complexity of this solution

Question

This is a tail-recursive solution for reversing a singly linked list. What is the auxiliary space occupied by this solution?

void reverseUtil(Node* curr, Node* prev, Node** head)
{
    if (curr->next==NULL) {
        *head = curr;
        curr->next = prev;
        return;
    }
    Node* next = curr->next;
    curr->next = prev;
    reverseUtil(next, curr, head);
}

void reverse(Node** head)
{
    if (head==NULL)
        return;
    reverseUtil(*head, NULL, head);
}

trincot · Answer 1 · 2021-04-05T12:36:53.360

First, your code should check that *head is not NULL before making the initial call to reverseUtil, so add this condition here:

if (head==NULL || *head==NULL)
    return;

This is indeed a case of tail recursion. All current mainstream C compilers perform tail call optimisation when the relevant option is set, and then the tail recursive calls are actually not increasing the stack space usage.

So provided that the compiler is instructed to perform this optimisation, the auxiliary space usage is O(1).

After the optimisation, the execution and space usage will be quite similar to what this iterative code would do:

void reverse(Node** head)
{
    if (head==NULL || *head==NULL)
        return;
    Node* curr = *head;
    Node* prev = NULL;
    while (true) {
        if (curr->next==NULL) {
            *head = curr;
            curr->next = prev;
            return;
        }
        Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
}

Auxiliary space complexity of this solution

1 Answers1