Print reverse of a Linked List without actually reversing
Given a linked list, print reverse of it using a recursive function. For example, if the given linked list is 1->2->3->4, then output should be 4->3->2->1.
Note that the question is only about printing the reverse. To reverse the list itself see this
Difficulty Level: Rookie
Algorithm
printReverse[head] 1. call print reverse for head->next 2. print head->dataImplementation:
|
// C++ program to print reverse of a linked list
#include
using namespace std;
/* Link list node */
class Node
{
public:
int data;
Node* next;
};
/* Function to reverse the linked list */
void printReverse[Node* head]
{
// Base case
if [head == NULL]
return;
// print the list after head node
printReverse[head->next];
// After everything else is printed, print head
cout data data = new_data;
/* link the old list off the new node */
new_node->next = [*head_ref];
/* move the head to point to the new node */
[*head_ref] = new_node;
}
/* Driver code*/
int main[]
{
// Let us create linked list 1->2->3->4
Node* head = NULL;
push[&head, 4];
push[&head, 3];
push[&head, 2];
push[&head, 1];
printReverse[head];
return 0;
}
// This code is contributed by rathbhupendra
|
|
// C program to print reverse of a linked list
#include
#include
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* Function to reverse the linked list */
void printReverse[struct Node* head]
{
// Base case
if [head == NULL]
return;
// print the list after head node
printReverse[head->next];
// After everything else is printed, print head
printf["%d ", head->data];
}
/*UTILITY FUNCTIONS*/
/* Push a node to linked list. Note that this function
changes the head */
void push[struct Node** head_ref, char new_data]
{
/* allocate node */
struct Node* new_node =
[struct Node*] malloc[sizeof[struct Node]];
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = [*head_ref];
/* move the head to point to the new node */
[*head_ref] = new_node;
}
/* Driver program to test above function*/
int main[]
{
// Let us create linked list 1->2->3->4
struct Node* head = NULL;
push[&head, 4];
push[&head, 3];
push[&head, 2];
push[&head, 1];
printReverse[head];
return 0;
}
|
|
// Java program to print reverse of a linked list
class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node next;
Node[int d] {data = d; next = null; }
}
/* Function to print reverse of linked list */
void printReverse[Node head]
{
if [head == null] return;
// print list of head node
printReverse[head.next];
// After everything else is printed
System.out.print[head.data+" "];
}
/* Utility Functions */
/* Inserts a new Node at front of the list. */
public void push[int new_data]
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node[new_data];
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*Driver function to test the above methods*/
public static void main[String args[]]
{
// Let us create linked list 1->2->3->4
LinkedList llist = new LinkedList[];
llist.push[4];
llist.push[3];
llist.push[2];
llist.push[1];
llist.printReverse[llist.head];
}
}
/* This code is contributed by Rajat Mishra */
|
|
# Python3 program to print reverse
# of a linked list
# Node class
class Node:
# Constructor to initialize
# the node object
def __init__[self, data]:
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__[self]:
self.head = None
# Recursive function to print
# linked list in reverse order
def printrev[self, temp]:
if temp:
self.printrev[temp.next]
print[temp.data, end = ' ']
else:
return
# Function to insert a new node
# at the beginning
def push[self, new_data]:
new_node = Node[new_data]
new_node.next = self.head
self.head = new_node
# Driver code
llist = LinkedList[]
llist.push[4]
llist.push[3]
llist.push[2]
llist.push[1]
llist.printrev[llist.head]
# This code is contributed by Vinay Kumar[vinaykumar71]
|
|
// C# program to print reverse of a linked list
using System;
public class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
public int data;
public Node next;
public Node[int d]
{
data = d; next = null;
}
}
/* Function to print reverse of linked list */
void printReverse[Node head]
{
if [head == null] return;
// print list of head node
printReverse[head.next];
// After everything else is printed
Console.Write[head.data + " "];
}
/* Utility Functions */
/* Inserts a new Node at front of the list. */
public void push[int new_data]
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node[new_data];
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/*Driver function to test the above methods*/
public static void Main[String []args]
{
// Let us create linked list 1->2->3->4
LinkedList llist = new LinkedList[];
llist.push[4];
llist.push[3];
llist.push[2];
llist.push[1];
llist.printReverse[llist.head];
}
}
// This code has been contributed by Rajput-Ji
|
|
// Javascript program to print reverse of a linked list
var head; // head of list
/* Linked list Node */
class Node {
constructor[val] {
this.data = val;
this.next = null;
}
}
/* Function to print reverse of linked list */
function printReverse[ head] {
if [head == null]
return;
// print list of head node
printReverse[head.next];
// After everything else is printed
document.write[head.data + " "];
}
/* Utility Functions */
/* Inserts a new Node at front of the list. */
function push[new_data] {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
new_node = new Node[new_data];
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Driver function to test the above methods */
// Let us create linked list 1->2->3->4
push[4];
push[3];
push[2];
push[1];
printReverse[head];
// This code contributed by Rajput-Ji
|
Output:
4 3 2 1Time Complexity: O[n]
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Reverse a linked list
Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.
Examples:
Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULLInput: Head of following linked list
1->2->3->4->5->NULL
Output: Linked list should be changed to,
5->4->3->2->1->NULLInput: NULL
Output: NULL
Input: 1->NULL
Output: 1->NULL
Implementing Your Own Linked List on Interviews
Since using existing Java classes is now allowed on Programming Job interviews, you need to create your own to write code. For this example, I have created our own singly linked list class. Similar to java.util.LinkedListalso contains a nested static class Node, which represents a node in the linked list.This class contains an integer attribute to hold the data part and another Node reference to point to the next one in the list. If you want to create a Generic linked list, you should replace int with T, a generic type, as shown here.
In order to demonstrate that our reverse method is working, we will not only have to create a linked list but also need to populate the linked list. In order to populate, you need to implement the add[] method on the singly linked list.
You have two choices, either add the element at the head or at the tail, adding an element to the head is easy as it doesn't require a traversal till the end but if you want to create a list that contains elements in the order they are added then we need to add nodes at the end of the linked list.
I have also created a print[] method to print all nodes of the singly linked list, separated by space. This method is very useful to demonstrate that our reverse method is actually working or not, as you can print the linked list before and after reversal.
If you struggle with implementing essential data structures like a linked list, binary tree, the hash table in your own code on any programming language like Java then I suggest you joinAlgorithms and Data Structures - Part 1 and 2courses on Pluralsight. They will not only help you to write your data structure but also how to calculate time and space complexity.
Algorithm –reverse single linked list in java [iterative algorithm]
- head variable denotes head of single linked list.
- Take couple of temporary variables
- next = null
- prev = null
- next = head.next [Step 1]
- save reference of subsequent node in next variable
- head.next = prev[node reversed] [Step 2]
- prev = head [Step 3]
- head = next [head points to second node] [Step 4]
Fig 2: Reverse nodes in single linked list
Nowapply the algorithm to reverse the linked list. Once we apply the above algorithm to complete linked list, we will get the reverse linked list as shown in Fig 3
Fig 3: Reversed single linked list
Time complexity of algorithm is O[n].
Introduction to the problem statement
Given a singly-linked list, print it in reverse order without actually reversing it. The only restriction is that you can’t reverse the original linked list.
Let us understand this problem with an example:-
Output -
According to the problem, we only need to print it in reverse order.
To specify, you must begin printing the data from the tail and work your way up to the head of the list.
To reverse the list itself, refer to thisproblem.
Before you go further, we recommend you try to implement the problem on your own.
Now that you have understood the problem let us switch to the possible methods to deal with the problem.