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:

• To see how we can print the reverse of the linked list using stack-based technique, check out the article Program To Reverse A Linked List Using Stack.
• This method requires extra space for the stack.

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 4^th node, then the 3^rd, then the 2^nd and finally the 1^st 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 i^th node.
  • Now, how will we print the i^th 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 i^th 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

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;
    new_node->next = (*head_ref);
    (*head_ref)    = new_node;
}
 
/* Counts no. of nodes in linked list */
int getCount(struct Node* head)
{
    int count = 0;  // Initialize count
    struct Node* current = head;  // Initialize current
    while (current != NULL)
    {
        count++;
        current = current->next;
    }
    return count;
}
 
/* Takes head pointer of the linked list and index
    as arguments and return data at index*/
int getNth(struct Node* head, int n)
{
    struct Node* curr = head;
    for (int i=0; i<n-1 &&="" curr="" !="NULL;" i++)="">next;
    return curr->data;
}
 
void printReverse(struct Node *head)
{
    // Count nodes
    int n = getCount(head);
 
    for (int i=n; i>=1; i--)
        printf("%d ", getNth(head, i));
}
 
/* Driver program to test count function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
 
    /* Use push() to construct below list
     1->2->3->4->5 */
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
 
    printReverse(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();
}
}

class Node:
    
    def __init__(self, data):
        self.data = data
        self.next = None
    
def push( head_ref, new_data):
    new_node = Node(new_data)
    new_node.next = head_ref
    head_ref = new_node
    return head_ref

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

def getNth(head, n):
    curr = head
    i = 0
    while i < n - 1 and curr != None:
        curr = curr.next
        i += 1
    return curr.data

def printReverse(head):

    n = getCount(head)
    
    for i in range(n, 0, -1):
        print(getNth(head, i), end = ' ')
    
if __name__=='__main__':
    
    head = None

    head = push(head, 8)
    head = push(head, 6)
    head = push(head, 4)
    head = push(head, 2)

    printReverse(head)

Output

8 6 4 2

Time Complexity: O(n²), 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.