Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Print the reverse of a linked list without extra space and modifications

Last Updated on June 6, 2022 by Ria Pathak

### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this problem, we are given a singly linked list, and we need to print the reverse of the linked list without using any extra space and without modifying the list.

### Problem Statement Understanding

The problem statement is self-explanatory, and we just have to print the reverse of the given linked list.

Suppose the given list is 1 → 2 →3 → 4.

• So the reverse of the above given linked list will be: 4 3 2 1.

Note: Now, the catch is that we cannot use extra space or modify the given list.

Let us have a look at what we could do if there wasn’t any constraint.

We can reverse the linked list either iteratively or recursively:

• To see how we can reverse the list, check out the article Reversing a linked list.
• In both recursive and iterative reversal, list modification occurs, and also in the recursive reversal, we require the recursion stack.

We can use Stack-based technique to print the reverse of a linked list:

According to our problem constraint, we cannot modify the list or use extra space, so we cannot use the above 2 approaches.

Input: 2 → 4 → 6 → 8
Output: 8 6 4 2

Explanation: As we can see, the reverse of the linked list has been printed.

So, how should we approach this problem?

• Can we use the length of the linked list? Yes. How?
• Let us have a look at the approach and get a clearer idea.

Let’s move to the approach section.

### Approach

Our approach is going to be pretty straightforward.

How can we utilize the length of the list?

• Well, what if first, we find the length of the list len, and then we print the elements at len, len – 1, len – 2, and so on up to 1.

Suppose the given list is 1 – > 2 – > 3 – > 4.

• The length of the list is 4.
• First, we will print the 4th node, then the 3rd, then the 2nd and finally the 1st node.
• In this manner, we are not using any extra space or modifying the list, and also we are completing our task of printing the elements of the list in reverse order.

Now, you might be thinking that we cannot traverse the singly linked list in reverse order, so how will we print the node in reverse order?

• The answer is that we will be using nested for loops, and to understand it more clearly, how we will be using nested loops, jump on to the algorithm section.

Let’s see the approach in more detail under algorithm section.

### Algorithm

• Create a variable len and initialize it with 0.

• Create a node temp and make it point to the head.

• Now, traverse the list with the help of temp and keep incrementing len by 1 for every node.

• After the traversal, the variable len will have the length of the list.

• Now, write a for loop from len to 1 [for (int i=len; i>=1; i–)], and for every iteration, do the following:

• Print the ith node.
• Now, how will we print the ith node?
• Point curr to the head.
• We will traverse from 0 to i-1 using a for loop [for (int j=0; j<i-1 && curr != NULL; j++)], and will keep incrementing curr.
• After the traversal, the curr will be standing at the ith node. We will simply print curr->data.
• To see all the above steps check function getithNode in code.
• In this way, the reverse of the list will the printed without any extra space usage and modifications.

### Code Implementation

```#include<stdio.h>
#include<stdlib.h>

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

/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->data  = new_data;
}

/* Counts no. of nodes in linked list */
{
int count = 0;  // Initialize count
struct Node* current = head;  // Initialize current
while (current != NULL)
{
count++;
current = current->next;
}
return count;
}

as arguments and return data at index*/
int getNth(struct Node* head, int n)
{
for (int i=0; i<n-1 &&="" curr="" !="NULL;" i++)="">next;
return curr->data;
}

{
// Count nodes

for (int i=n; i>=1; i--)
}

/* Driver program to test count function*/
int main()
{

/* Use push() to construct below list
1->2->3->4->5 */

return 0;
}
```
```public class PrepBytes
{
/* Structure of a linked list node */
static class Node
{
int data;
Node next;
};

/* Using this function we will push a node at head of the linked list */
static void push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
}

/* Using this function we will get the length of the linked list */
{
int count = 0;
while (current != null)
{
count++;
current = current.next;
}
return count;
}

/* Using this function we will get the ith node from the linked list */
static int getithNode(Node head, int i)
{
for (int j = 0; j < i - 1 && curr != null; j++){
curr = curr.next;
}
return curr.data;
}

/* Using this function we will print the reverse of the linked list */
static void printRev()
{

for (int i = len; i >= 1; i--)
}

public static void main(String[] args)
{

printRev();
}
}
```
```class Node:

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

new_node = Node(new_data)

count = 0
while (current != None):
count += 1
current = current.next
return count

i = 0
while i < n - 1 and curr != None:
curr = curr.next
i += 1
return curr.data

for i in range(n, 0, -1):
print(getNth(head, i), end = ' ')

if __name__=='__main__':

```

#### Output

8 6 4 2

Time Complexity: O(n2), as nested list traversal is needed.
[forminator_quiz id=”5347″]

So, in this article, we have tried to explain the technique to print the reverse of a linked list without any extra space or modifying the list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.