# Printing a singly linked list with time complexity O(n) and space complexity O(sqrt(n)) [closed]

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*));
int i;
for(i = 0; i<list_size; ++i, temp=temp->next)
pointer_array[i] = temp;
for(i = list_size - 1; i>=0; --i)
printf("%d\n", pointer_array[i]->data);
free(pointer_array);
}

int size(List* l)
{
int count = 0;
while(temp!= NULL)
{
++count;
temp = temp->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?

## closed as off-topic by Quuxplusone, ferada, hjpotter92, Pimgd, BenVlodgiOct 27 '15 at 14:21

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Quuxplusone, ferada, hjpotter92, Pimgd, BenVlodgi
If this question can be reworded to fit the rules in the help center, please edit the question.

• This is off-topic for "Code Review"; perhaps "Programming Puzzles and Code Golf" would be the right StackExchange for it? But to give you a hint on the puzzle: Read up on skip lists, and on the "Two Egg Problem". Once you understand those puzzles, you'll definitely be able to solve this one with a little bit of thought. – Quuxplusone Oct 27 '15 at 5:48

# 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 < n; i++, p = p->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 >= 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<size; i++) {
List *newNode = malloc(sizeof(List));

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.