1
\$\begingroup\$

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->head;
    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;
    Node* temp = l->head;
    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?

\$\endgroup\$

closed as off-topic by Quuxplusone, ferada, hjpotter92, Pimgd, BenVlodgi Oct 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.

  • \$\begingroup\$ 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. \$\endgroup\$ – Quuxplusone Oct 27 '15 at 5:48
2
\$\begingroup\$

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));
        newNode->data = head->data;
        newNode->next = ret;
        ret = newNode;
        head = head->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.

\$\endgroup\$
  • \$\begingroup\$ Yes, this will definitely do the job but there is also a condition placed that the list is read only and hence, cannot be modified. Sorry that I forgot to mention about it! \$\endgroup\$ – Sagar B Hathwar Oct 27 '15 at 6:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.