Print Reverse Of A Linked List Without Actually Reversing it

Last Updated on March 12, 2022 by Ria Pathak

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
}

#include
#include
  
/* Link list node */
struct Node
{
    int data;
    struct Node* next;
};
  
/* Function to reverse the linked list */
void printReverse(struct Node* head)
{
    // Base case 
    if (head == NULL)
       return;
 
    // print the list after head node
    printReverse(head->next);
 
    // After everything else is printed, print head
    printf("%d  ", head->data);
}
  
/*UTILITY FUNCTIONS*/
/* Push a node to linked list. Note that this function
  changes the head */
void push(struct Node** head_ref, char new_data)
{
    /* allocate node */
    struct Node* new_node =
            (struct Node*) malloc(sizeof(struct Node));
  
    /* put in the data  */
    new_node->data  = new_data;
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);  
  
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
  
/* Driver program to test above function*/
int main()
{
    // Let us create linked list 1->2->3->4
    struct Node* head = NULL;   
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
   
    printReverse(head);
    return 0;
}

class Reverse
{
	Node head; 
	class Node
	{
		int data;
		Node next;
		Node(int d) {data = d; next = null; }
	}
	/* Function to print reverse of linked list */
	void printReverse(Node head)
	{
		if (head == null) return;

		// print list of head node
		printReverse(head.next);

		// After everything else is printed
		System.out.print(head.data+" ");
	}
	public void push(int new_data)
	{
		Node new_node = new Node(new_data);
		new_node.next = head;
		head = new_node;
	}
	public static void main(String args[])
	{
		Reverse llist = new Reverse();
		llist.push(4);
		llist.push(3);
		llist.push(2);
		llist.push(1);

		llist.printReverse(llist.head);
	}
}

class Node:

	def __init__(self, data):
		
		self.data = data
		self.next = None

class LinkedList:

	def __init__(self):
		
		self.head = None

	def push(self, new_data):
		
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def printReverse(self):
		
		temp = self.head
		st = []
		while(temp):
			st.append(temp)
			temp = temp.next
			
		while st:
			node = st[-1]
			st.pop()
			print(node.data, end=" ")

if __name__ == '__main__':
	
	l = LinkedList()
	
	for i in range(5,0,-1):
		l.push(i)
	l.printReverse()

Output

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

[forminator_quiz id=”3867″]
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.