Print Reverse Of A Linked List Without Actually Reversing it

Problem statement

Given a singly linked list. Write a function to print it in reverse order. The only restriction is that you can’t reverse the original linked list.

Problem statement Understanding

Let us understand this problem with an example:
Let’s say we have the given linked list as,

According to the problem we need to print it in reverse order. Reverse order means we have to print the values of nodes from right to left.

So the desired output for this linked list will be 5 4 3 2 1.

We need to do this without reversing the given linked list.

Hope that you have understood the problem. Now try to come up with an approach.

If we were allowed to reverse the linked list, then it would be simple. But here we aren’t allowed to do so. So, try to think how we should approach this problem?

Approach 1 (Using a stack)

Let’s see how a stack works.

It follows the LIFO(last in first out) principle. This means the element inserted most recently will come out first. And similarly, if we extract elements from the stack, we will get them in the reverse order of insertion. This is exactly what we need.

So, due to its LIFO property, a stack is able to store elements in reverse order of their insertion and hence can be used to solve our problem.

We can simply traverse the linked list and push the value stored in the nodes one by one into the stack. When the traversal is complete, we would have the linked list’s data in reverse order in the stack. Now, we can, one by one, extract the top element from the stack and print them and then pop the elements from the stack.

Algorithm

  • Create an empty stack
  • Traverse the linked list and push the value in the nodes to the stack.
  • After iteration, one by one pop the elements from the stack and print them.
  • We would have our linked list printed in reverse order.

Code Implementation:

#include
using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int value){
   	 val = value;
   	 next = NULL;
    }
};

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void printList(Node* head){
    Node* i = head;
    while(i){
   	 cout<val<<" ";
   	 i = i->next;
    }
    cout<<"\n";
}


// function to print linked list in
// reverse order using stack
void printReverse(Node* head){
    stack st;

    Node* i = head;
    while(i){
   	 st.push(i->val);
   	 i = i->next;
    }

    while(!st.empty()){
   	 cout<


						 

Output

5 4 3 2 1

Time complexity: O(N), as we are doing a complete traversal of the linked list.
Space complexity: O(N), as we are using a stack to store all the nodes.

Where N is the number of nodes in the linked list.

The above algorithm does the work, but it requires extra space. So, can we think of some way to avoid using extra space?

Approach 2 (Using recursion)

If we traverse a linked list using recursion, we have a choice if we want to print the node before traversing the rest of the nodes or after doing so. So, if we print a node after traversing the remaining nodes, we would achieve our task of printing the linked list in reverse order.

Algorithm

  • Base case - If the linked list is empty do nothing and simply return from the function.
  • For the current node, before printing, it recursively call the same function for the next node. This will print all the nodes after the current node.
  • Now we just print the current node’s value.

We will have our linked list printed in reverse order.

Code Implementation:


#include
using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int value){
   	 val = value;
   	 next = NULL;
    }
};

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void printList(Node* head){
    Node* i = head;
    while(i){
   	 cout<val<<" ";
   	 i = i->next;
    }
    cout<<"\n";
}

// recusrive function to print
// linked list in reverse order
void printReverse(Node* head){
    if(head==NULL) return;

    printReverse(head->next);
    cout<val<<" ";
}

int main(){
    Node* head = NULL;

    push_front(&head, 5);
    push_front(&head, 4);
    push_front(&head, 3);
    push_front(&head, 2);
    push_front(&head, 1);
    
    cout<<”Our linked list:\n”;
    printList(head);
    // 1 2 3 4 5

    cout<<”Printing Linked list in reverse order:\n”;
    printReverse(head);
    // 5 4 3 2 1
}

Output

Our linked list:
1 2 3 4 5
Printing Linked list in reverse order:
5 4 3 2 1


Space complexity: O(n), due to the recursive function call stack.

Through this article, we discussed two approaches to print the reverse of a linked list without actually reversing it. Problems like these are good for strengthening your concepts in LinkedList. I would highly recommend you to practice more such problems from Linked Lists.

Previous post Add two numbers represented by linked lists | Set 1
Next post Program To Reverse A Linked List Using Stack

Leave a Reply

Your email address will not be published. Required fields are marked *