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 <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void printReverse(struct Node** head_ref, int n)
{
int j = 0;
struct Node* current = *head_ref;
while (current != NULL) {
for (int i = 0; i < 2 * (n - j); i++)
printf(" ");
printf("%d\r", current->data);
current = current->next;
j++;
}
}
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;
}
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, 1);
push(&head, 2);
push(&head, 3);
push(&head, 4);
push(&head, 5);
push(&head, 6);
printf("Given linked list:\n");
int n = printList(head);
printf("\nReversed Linked list:\n");
printReverse(&head, n);
printf("\n");
return 0;
}
|
C++
#include <iostream>
#include <cstring>
using namespace std;
class Node {
public:
int data;
Node *next;
Node(int val)
{
data = val;
next = nullptr;
}
};
void printReverse(Node *head, int n)
{
int j = 0;
Node *current = head;
while (current != nullptr) {
for (int i = 0; i < 2 * (n - j); i++)
cout << " ";
cout << "\r" << current->data;
current = current->next;
j++;
}
}
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)
{
int i = 0;
Node *temp = head;
while (temp != nullptr)
{
cout << temp->data << " ";
temp = temp->next;
i++;
}
return i;
}
int main()
{
Node *head = nullptr;
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;
int n = printList(head);
cout << "Reversed Linked list: " << endl;
printReverse(head, n);
cout << endl;
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class Node {
int data;
Node next;
Node(int val)
{
data = val;
next = null;
}
}
public class GFG {
static void printReverse(Node head, int n)
{
int j = 0;
Node current = head;
while (current != null) {
for (int i = 0; i < 2 * (n - j); i++)
System.out.print(" ");
System.out.print(" " + current.data);
current = current.next;
j++;
}
}
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[])
{
Node head = null;
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: ");
int n = printList(head);
System.out.println("\nReversed Linked list: ");
printReverse(head, n);
System.out.println();
}
}
|
C#
using System;
public class Node {
public int data;
public Node next;
public Node(int val)
{
data = val;
next = null;
}
}
public class GFG
{
static void printReverse(Node head, int n)
{
int j = 0;
Node current = head;
while (current != null) {
for (int i = 0; i < 2 * (n - j); i++)
Console.Write(" ");
Console.Write("\r" + current.data);
current = current.next;
j++;
}
}
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)
{
Console.Write(temp.data + " ");
temp = temp.next;
i++;
}
return i;
}
public static void Main(String []args)
{
Node head = null;
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: ");
int n = printList(head);
Console.WriteLine("Reversed Linked list: ");
printReverse(head, n);
Console.WriteLine();
}
}
|
Python3
class Node:
def __init__(self):
self.data= 0
self.next=None
def printReverse( head_ref, n):
j = 0
current = head_ref
while (current != None):
i = 0
while ( i < 2 * (n - j) ):
print(end=" ")
i = i + 1
print( current.data, end = "\r")
current = current.next
j = j + 1
def push( head_ref, new_data):
new_node = Node()
new_node.data = new_data
new_node.next = (head_ref)
(head_ref) = new_node
return head_ref;
def printList( head):
i = 0
temp = head
while (temp != None):
print( temp.data,end = " ")
temp = temp.next
i = i + 1
return i
head = None
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:")
n = printList(head)
print("\nReversed Linked list:")
printReverse(head, n)
print()
|
Javascript
<script>
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
function printReverse(head, n) {
let j = 0;
let current = head;
while (current !== null) {
for (let i = 0; i < 2 * (n - j); i++) {
process.stdout.write(" ");
}
process.stdout.write("\r" + current.data);
current = current.next;
j++;
}
}
function push(head, data) {
const new_node = new Node(data);
new_node.next = head;
head = new_node;
return head;
}
function printList(head) {
let i = 0;
let temp = head;
while (temp !== null) {
process.stdout.write(temp.data + " ");
temp = temp.next;
i++;
}
return i;
}
(function main() {
let head = null;
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: ");
let n = printList(head);
console.log("\nReversed Linked list: ");
printReverse(head, n);
console.log();
})();
</script>
|
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
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!