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

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.

Dry Run

![](https://blog.prepbytes.com/wp-content/uploads/2021/09/p_1-39.png)

![](https://blog.prepbytes.com/wp-content/uploads/2021/09/p_2-38.png)

Code Implementation

#include
#include

/* Structure of a linked list node */
struct Node
{
    int data;
    struct Node* next;
};

/* Using this function we will push a node at head of the linked 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;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

/* Using this function we will get the length of the linked list */
int getLength(struct Node* head)
{
    int count = 0; 
    struct Node* current = head; 
    while (current != NULL)
    {
        count++;
        current = current->next;
    }
    return count;
}

/* Using this function we will get the ith node from the linked list */
int getithNode(struct Node* head, int i)
{
    struct Node* curr = head;
    for (int j=0; jnext;
    }
    return curr->data;
}

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

    int len = getLength(head);

    for (int i=len; i>=1; i--)
        printf("%d ", getithNode(head, i));
}

int main()
{
    struct Node* head = NULL;
    push(&head, 8);
    push(&head, 6);
    push(&head, 4);
    push(&head, 2);

    printRev(head);

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

/* 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;
    new_node.next = (head_ref);
    (head_ref) = new_node;
    head = head_ref;
}

/* Using this function we will get the length of the linked list */
static int getLength(Node head)
{
    int count = 0; 
    Node current = head;
    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)
{
    Node curr = head;
    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()
{
    int len = getLength(head);

    for (int i = len; i >= 1; i--)
        System.out.printf("%d ", getithNode(head, i));
}

public static void main(String[] args)
{
    head = null;
    push(head, 8);
    push(head, 6);
    push(head, 4);
    push(head, 2);

    printRev();
}
}

Output

8 6 4 2

Time Complexity: O(n2), as nested list traversal is needed.

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.

Previous post ConcurrentLinkedQueue isEmpty() method
Next post Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?

Leave a Reply

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