Print singly linked list in reverse order

Question

Okay, this was the bonus question in CMPS 280's test at southeastern Louisiana Univ. Print singly linked list in reverse in three lines. Any ideas?

Answer 1

C implementation of your bonus question, in three lines:

#include <stdio.h>

struct node {
    int data;
    struct node* next;
};

void ReversePrint(struct node* head) {
    if(head == NULL) return;
    ReversePrint(head->next);
    printf("%d ", head->data);
}

int main()
{
    struct node first;
    struct node second;
    struct node third;

    first.data = 1;
    second.data = 2;
    third.data = 3;

    first.next = &second;
    second.next = &third;

    ReversePrint(&first); // Should print: 3 2 1
    printf("\n");

    return 0;
}

Answer 2

If you are allowed to use another Data Structure, then use a Stack.

Step 1: Traverse the linked list from the head node and put the key into the stack, till you reach the last node. This will take O(n) time.

Step 2 : Pop the elements out from the stack. This will take O(1) time.

Therefore, code will be

while(head != null){
stack.push(head.val);
head = head.next;
}
while(stack.isEmpty() != true){
stack.pop();
}

Answer 3

Generally, when asking for help on SO, you should always try to do the problem yourself first. Then, if you are stuck, come here with what you have done so far and clearly show what your problem is to maximize your chances of getting help.

How to ask a good question on SO

However, since it is a past exam question and my answer wont help you cheat :), here's pseudo-code how you can do it recursively:

reversePrint(head)
    if head is null then return // Line 1: base case
    reversePrint(head.next)     // Line 2: print the list after head
    print(head.data)            // Line 3: print head