An interesting method to print the reverse of a linked list.

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 will be given a linked list and are required to print the reverse of the linked list without using conventional methods.

Problem Statement Understanding

This is an interesting problem. According to the problem statement, we will have to print the reverse of the given linked list without using any conventional method for reversing the linked list.

If the given linked list: 23 → 12 → 2 → 10

  • Then the reverse of the linked list is: 10 → 2 → 12 → 23.
  • Our output will be the print of the reverse of the linked list, which will be 10, 2, 12, 23.

If the given linked list is: 1 → 3 → 5 → 7 → 9 → 11 → 13 → 15

  • In this case, our output will be 15, 13, 11, 9, 7, 5, 3, 1.
Some more examples

Sample Input 1: 1 → 2 → 3 → 4
Sample Output 1: 4, 3, 2, 1

Sample Input 2: 2 → 4 → 6 → 8 → 10
Sample Output 2: 10, 8, 6, 4, 2

Explanation: We are printing the reverse of the given linked list.

Well, reversing a linked list is pretty easy, right? But here, we can’t reverse the linked list. So, how should we approach the problem?

  • The answer is Carriage return ("r"). Whenever we use "r", it commands the printer to move the position of the cursor to the first position on the same line.

Let us have a glance at the approach.

Approach

The approach is going to be pretty straightforward.

  • First, we will find out the length of the linked list.
  • Then, we will print (n-1) blank spaces and then print the 1st element then the carriage return "r", further again we will print (n-2) blank spaces and the 2nd element and then again carriage return "r" and so on... until we reach the end of the list.

Note: What we are doing above is, after printing (n-1) blank spaces and then the element, we are commanding the cursor to jump to the start of the line. So that, when the next printing portion happens, the (n-2) spaces are given from the start of the line and then the next element is printed and hence in this way the printing will happen in a reverse fashion.

Algorithm

  • Find the length of the given linked list, and store it in n.
  • Initialize a variable j with 0.
  • Now initialize a pointer curr with head and start traversing the list using curr.
  • While traversing the list:
    • Run a for loop to print the proper number of blank spaces before printing the current node’s data. Actually, print (n-j) spaces, because that is the proper spacing which will give the perfect look of reverse printing.
    • After printing the blank spaces, print the current’s nodes data and use carriage return (printf(“%d\r”, curr→data)).
    • Increment the current node by curr = curr→next.
    • Increment j by 1.
  • This way, our list will get printed in reverse order.

Dry Run

Code Implementation

#include 
#include 

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

/* Using this function we will be printing the reverse of the given linked list */
void printReverse(struct Node** head, int n)
{
    int j = 0;
    struct Node* curr = *head;
    while (curr != NULL) {
        for (int i = 0; i <  (n - j); i++)
            printf(" ");
 
        printf("%d\r", curr->data);
        curr = curr->next;
        j++;
    }
}

/* Using this function we will be adding a new node to the head of the given linked list */
void push(struct Node** head, int new_data)
{
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
 
    new_node->data = new_data;
    new_node->next = (*head);
    (*head) = new_node;
}
 
/* Using this function we will be printing the elements of the given linked list */
int printList(struct Node* head)
{ 
    int i = 0;
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d  ", temp->data);
        temp = temp->next;
        i++;
    }
    return i;
}

int main()
{
    struct Node* head = NULL;
    push(&head, 10);
    push(&head, 2);
    push(&head, 12);
    push(&head, 23);

 
    printf("Printing original given linked list: \n");
    int n = printList(head);

    printf("\nPrinting reversed linked list: \n");
    printReverse(&head, n);
    printf("\n");
    return 0;
}
import java.io.*;
import java.util.*;

/* Structure of a linked list node */
class Node {
    int data;
    Node next;
    Node(int val)
    {
        data = val;
        next = null;
    }
}

public class PrepBytes
{

/* Using this function we will be printing the reverse of the given linked list */
static void printReverse(Node head, int n)
{
        int j = 0;
        Node curr = head;
        while (curr != null) {

            for (int i = 0; i < (n-j); i++)
                System.out.print(" ");

            System.out.print(curr.data  +"\r" );

            curr = curr.next;
            j++;
        }
}

/* Using this function we will be adding a new node to the head of the given linked list */
static Node push(Node head, int data)
{
        Node new_node = new Node(data);
        new_node.next = head;
        head = new_node;

        return head;
}

/* Using this function we will be printing the elements of the given linked list */
static int printList(Node head)
{
        int i = 0;
        Node temp = head;
        while (temp != null)
        {
                System.out.print(temp.data + " ");
                temp = temp.next;
                i++;
        }
        return i;
}


public static void main(String args[])
{
        Node head = null;
        head = push(head, 10);
        head = push(head, 2);
        head = push(head, 12);
        head = push(head, 23);

        System.out.println("Printing original given linked list: ");

        int n = printList(head);

        System.out.println();
        System.out.println("Printing reversed linked list: ");
        printReverse(head, n);
        System.out.println();
}
}

Output

Printing original given linked list:
23 12 2 10
Printing reversed Linked list:
10 2 12 23

Time Complexity: O(n), as list traversal is needed

So, in this article, we have tried to explain an interesting method to print the reverse of a linked list. The unique constraints of this problem are what makes this problem an important one for coding interviews. 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 Remove duplicates from a sorted linked list
Next post Merge two sorted linked lists

Leave a Reply

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