Printing a singly linked list with time complexity O(n) and space complexity O(sqrt(n)) My aim is to write a method which prints contents of a singly linked list in reverse order with time complexity \$O(n)\$ and space complexity \$O(\sqrt{n})\$. The best I could come up with is to store the pointers to nodes in an array and print it in reverse order.

void display_reverse(List *l)
{
    int list_size = size(l);
    Node** pointer_array = malloc(list_size*sizeof(Node*));
    Node* temp = l-&gt;head;
    int i;
    for(i = 0; i&lt;list_size; ++i, temp=temp-&gt;next)
        pointer_array[i] = temp;
    for(i = list_size - 1; i&gt;=0; --i)
        printf("%d\n", pointer_array[i]-&gt;data);
    free(pointer_array);
}

int size(List* l)
{
    int count = 0;
    Node* temp = l-&gt;head;
    while(temp!= NULL)
    {
        ++count;
        temp = temp-&gt;next;
    }

    return count;
}


Is there a better way of doing it, without modifying the list in any way?  There is another option where time complexity is \$O(n \log n)\$ and space complexity is \$O(\log n)\$. How can I go about solving this?
Reverse the list

A quick search on the internet will show you that you can reverse a linked list in-place using \$O(n)\$ time and \$O(1)\$ space.  All you need to do after that is print the list in order:

void display_reverse(List *list)
{
    list = reverseList(list);
    printList(list);
    list = reverseList(list);
}


This whole function will take \$O(n)\$ time and \$O(1)\$ space.

Without modifying the list

If you can't modify the list, you can do it by making copies of part of the list.  If the list is \$n\$ items, you can make \$\sqrt n\$ sized sublist copies, and reverse/print them one at a time.  To do that, you will need to use a \$\sqrt n\$ sized array to keep track of these sublists.  Here is what the program would look like:

void display_reverse(const List *list)
{
    int n     = countItemsInList(list);
    int sqrtn = sqrt(n);
    const List *subLists[sqrtn];
    const List *p;

    // Remember the head of each sqrtn sized sublist
    for (int i=0, p = list; i &lt; n; i++, p = p-&gt;next) {
        if (i % sqrtn == 0)
            subLists[i / sqrtn] = p;
    }

    // Make a reversed copy of each subList and print it.
    for (int i=sqrtn-1; i &gt;= 0; i--) {
        int subListSize = sqrtn;
        if (i == sqrtn-1) {
            // The last subList size may be different.
            subListSize = n - (sqrtn-1) * sqrtn;
        }
        List *tempList = createReversedList(subList[i], subListSize);
        printList(tempList);
        freeList(tempList);
    }
}

static List *createReversedList(const List *head, int size)
{
    List *ret = NULL;

    for (int i=0; i&lt;size; i++) {
        List *newNode = malloc(sizeof(List));
        newNode-&gt;data = head-&gt;data;
        newNode-&gt;next = ret;
        ret = newNode;
        head = head-&gt;next;
    }
    return ret;
}


This program uses \$O(\sqrt n)\$ space because it uses one array of that size and one temporary list of that size.  It runs in \$O(n)\$ time.

You may want to round up using sqrtn = ceil(sqrt(n)).  That prevents the last sublist size from exceeding sqrtn, so it has a slightly better space utilization.