Open In App

An interesting method to print reverse of a linked list

Last Updated : 26 Dec, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

We are given a linked list, we need to print the linked list in reverse order.
Examples: 

Input : list : 5-> 15-> 20-> 25 
Output : Reversed Linked list : 25-> 20-> 15-> 5

Input : list : 85-> 15-> 4-> 20
Output : Reversed Linked list : 20-> 4-> 15-> 85

Input : list : 85
Output : Reversed Linked list : 85

For printing a list in reverse order, we have already discussed Iterative and Recursive Methods to Reverse.
In this post, an interesting method is discussed, that doesn’t require recursion and does no modifications to list. The function also visits every node of linked list only once.

Trick : Idea behind printing a list in reverse order without any recursive function or loop is to use Carriage return (“r”). For this, we should have knowledge of length of list. Now, we should print n-1 blank space and then print 1st element then “r”, further again n-2 blank space and 2nd node then “r” and so on.. 
Carriage return (“r”) : It commands a printer (cursor or the display of a system console), to move the position of the cursor to the first position on the same line.
 

C++




#include <iostream>
#include <cstring>
 
using namespace std;
 
// Represents node of a linked list
class Node {
public:
    int data;
    Node* next;
    Node(int val)
    {
        data = val;
        next = nullptr;
    }
};
 
void printReverse(Node* head)
{
    if (!head)
        return;
 
    printReverse(head->next);
 
    cout << head->data << " ";
}
 
Node* push(Node* head, int data)
{
    Node* new_node = new Node(data);
    new_node->next = head;
    head = new_node;
 
    return head;
}
 
int printList(Node* head)
{
    // i for finding the length of the list
    int i = 0;
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " ";
        temp = temp->next;
        i++;
    }
 
    return i;
}
 
// Driver code
int main()
{
    /* Start with the empty list */
    Node* head = nullptr;
 
    // list nodes are as 6 5 4 3 2 1
    head = push(head, 1);
    head = push(head, 2);
    head = push(head, 3);
    head = push(head, 4);
    head = push(head, 5);
    head = push(head, 6);
 
    cout << "Given linked list: " << endl;
    // printlist print the list and
    // return the size of the list
    int n = printList(head);
 
    // print reverse list
    cout << "\nReversed Linked list: " << endl;
    printReverse(head);
    cout << endl;
 
    return 0;
}


C




#include <stdio.h>
#include <stdlib.h>
 
// Represents node of a linked list
struct Node {
    int data;
    struct Node* next;
};
 
void printReverse(struct Node* head) {
    if (!head)
        return;
 
    printReverse(head->next);
 
    printf("%d ", head->data);
}
 
struct Node* push(struct Node* head, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = head;
    head = new_node;
 
    return head;
}
 
int printList(struct Node* head) {
    // i for finding the length of the list
    int i = 0;
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
        i++;
    }
 
    return i;
}
 
// Driver code
int main() {
    /* Start with the empty list */
    struct Node* head = NULL;
 
    // list nodes are as 6 5 4 3 2 1
    head = push(head, 1);
    head = push(head, 2);
    head = push(head, 3);
    head = push(head, 4);
    head = push(head, 5);
    head = push(head, 6);
 
    printf("Given linked list:\n");
    // printlist print the list and
    // return the size of the list
    int n = printList(head);
 
    // print reverse list
    printf("\nReversed Linked list:\n");
    printReverse(head);
    printf("\n");
 
    return 0;
}


Java




class Node {
    int data;
    Node next;
 
    Node(int val) {
        data = val;
        next = null;
    }
}
 
public class ReversePrint {
    static void printReverse(Node head) {
        if (head == null)
            return;
 
        printReverse(head.next);
 
        System.out.print(head.data + " ");
    }
 
    static Node push(Node head, int data) {
        Node new_node = new Node(data);
        new_node.next = head;
        head = new_node;
 
        return head;
    }
 
    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) {
        /* Start with the empty list */
        Node head = null;
 
        // list nodes are as 6 5 4 3 2 1
        head = push(head, 1);
        head = push(head, 2);
        head = push(head, 3);
        head = push(head, 4);
        head = push(head, 5);
        head = push(head, 6);
 
        System.out.println("Given linked list:");
        // printlist print the list and
        // return the size of the list
        int n = printList(head);
 
        // print reverse list
        System.out.println("\nReversed Linked list:");
        printReverse(head);
        System.out.println();
    }
}


Python3




class Node:
    def __init__(self, val):
        self.data = val
        self.next = None
 
def print_reverse(head):
    if not head:
        return
 
    print_reverse(head.next)
    print(head.data, end=" ")
 
def push(head, data):
    new_node = Node(data)
    new_node.next = head
    head = new_node
    return head
 
def print_list(head):
    i = 0
    temp = head
    while temp is not None:
        print(temp.data, end=" ")
        temp = temp.next
        i += 1
    return i
 
# Driver code
if __name__ == "__main__":
    # Start with the empty list
    head = None
 
    # list nodes are as 6 5 4 3 2 1
    head = push(head, 1)
    head = push(head, 2)
    head = push(head, 3)
    head = push(head, 4)
    head = push(head, 5)
    head = push(head, 6)
 
    print("Given linked list:")
    # printlist print the list and
    # return the size of the list
    n = print_list(head)
 
    # print reverse list
    print("\nReversed Linked list:")
    print_reverse(head)
    print()


C#




using System;
 
// Represents node of a linked list
public class Node {
    public int data;
    public Node next;
 
    public Node(int val) {
        data = val;
        next = null;
    }
}
 
public class ReversePrint {
    static void PrintReverse(Node head) {
        if (head == null)
            return;
 
        PrintReverse(head.next);
 
        Console.Write(head.data + " ");
    }
 
    static Node Push(Node head, int data) {
        Node new_node = new Node(data);
        new_node.next = head;
        head = new_node;
 
        return head;
    }
 
    static void PrintList(Node head) {
        Node temp = head;
        while (temp != null) {
            Console.Write(temp.data + " ");
            temp = temp.next;
        }
    }
 
    public static void Main() {
        /* Start with the empty list */
        Node head = null;
 
        // list nodes are as 6 5 4 3 2 1
        head = Push(head, 1);
        head = Push(head, 2);
        head = Push(head, 3);
        head = Push(head, 4);
        head = Push(head, 5);
        head = Push(head, 6);
 
        Console.WriteLine("Given linked list:");
        // printlist prints the list
        PrintList(head);
 
        // print reverse list
        Console.WriteLine("\nReversed Linked list:");
        PrintReverse(head);
        Console.WriteLine();
    }
}


Javascript




class Node {
    constructor(val) {
        this.data = val;
        this.next = null;
    }
}
 
function printReverse(head) {
    if (head === null)
        return;
 
    printReverse(head.next);
 
    console.log(head.data + " ");
}
 
function push(head, data) {
    let new_node = new Node(data);
    new_node.next = head;
    head = new_node;
 
    return head;
}
 
function printList(head) {
    let temp = head;
    while (temp !== null) {
        console.log(temp.data + " ");
        temp = temp.next;
    }
}
 
// Driver code
let head = null;
 
// list nodes are as 6 5 4 3 2 1
head = push(head, 1);
head = push(head, 2);
head = push(head, 3);
head = push(head, 4);
head = push(head, 5);
head = push(head, 6);
 
console.log("Given linked list:");
// printlist prints the list
printList(head);
 
// print reverse list
console.log("\nReversed Linked list:");
printReverse(head);
console.log();


Output: 

Given linked list:
6 5 4 3 2 1
Reversed Linked List:
1 2 3 4 5 6

Time Complexity: O(N).
Auxiliary Space: O(1), 

Input and Output Illustration : 
Input: 6 5 4 3 2 1 
1st Iteration _ _ _ _ _ 6 
2nd Iteration _ _ _ _ 5 6 
3rd Iteration _ _ _ 4 5 6 
4th Iteration _ _ 3 4 5 6 
5th Iteration _ 2 3 4 5 6 
Final Output 1 2 3 4 5 6
NOTE: Above program may not work on online compilers because they do not support anything like carriage return on their console.
Reference : 
StackOverflow/Carriage return


 



Like Article
Suggest improvement
Previous
Next
Share your thoughts in the comments

Similar Reads