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 <bits/stdc++.h>
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 << head->data << " ";
}
/*UTILITY FUNCTIONS*/
/* Push a node to linked list. Note that this function
changes the head */
void push(Node** head_ref, char new_data)
{
/* allocate node */
Node* new_node = new 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 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<stdio.h>
#include<stdlib.h>
/* 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
|
|
<script>
// 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
</script>
|
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
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.
Reverse a Linked List C++ Code (Iterative and Recursive)
Many of you must be familiar with the application of a linked list in the real world and its importance. We use linked lists to maintain a directory of names, dynamic allocation of memory, and create an implementation of essentials data structures like stacks and queues, and what not?
Knowing all this in this tutorial we are going to discuss the basic understanding of a linked list, and implement and analyze how to reverse a linked list in C++. Let’s get Kraken!
Print reverse of a Linked List without actually reversing in C language
The task is to print the reverse of a given linked list by using recursive function. The program must print the reverse but not reverse the list that means the order of the nodes remains the same
Here, the program will move head pointer containing the address of a first node to next node until the NULL is examined which is stored in last node of a list and printing the data of a head node.
Types of Linked List and Operation on Linked List
In the previous blog, we have seen the structure and properties of a Linked List. In this blog, we will discuss the types of a linked list and basic operations that can be performed on a linked list.
Types of Linked List
Following are the types of linked list
- Singly Linked List.
- Doubly Linked List.
- Circular Linked List.
Singly Linked List
A Singly-linked list is a collection of nodes linked together in a sequential way where each node of the singly linked list contains a data field and an address field that contains the reference of the next node.
The structure of the node in the Singly Linked List is
The nodes are connected to each other in this form where the value of the next variable of the last node is NULL i.e. next = NULL, which indicates the end of the linked list.
Doubly Linked List
A Doubly Linked List contains an extra memory to store the address of the previous node, together with the address of the next node and data which are there in the singly linked list. So, here we are storing the address of the next as well as the previous nodes.
The following is the structure of the node in the Doubly Linked List(DLL):
The nodes are connected to each other in this form where the first node has prev = NULL and the last node has next = NULL.
Advantages over Singly Linked List-
- It can be traversed both forward and backward direction.
- The delete operation is more efficient if the node to be deleted is given. (Think! you will get the answer in the second half of this blog)
- The insert operation is more efficient if the node is given before which insertion should take place. (Think!)
Disadvantages over Singly Linked List-
- It will require more space as each node has an extra memory to store the address of the previous node.
- The number of modification increase while doing various operations like insertion, deletion, etc.
Circular Linked List
A circular linked list is either a singly or doubly linked list in which there are no NULL values. Here, we can implement the Circular Linked List by making the use of Singly or Doubly Linked List. In the case of a singly linked list, the next of the last node contains the address of the first node and in case of a doubly-linked list, the next of last node contains the address of the first node and prev of the first node contains the address of the last node.
Advantages of a Circular linked list
- The list can be traversed from any node.
- Circular lists are the required data structure when we want a list to be accessed in a circle or loop.
- We can easily traverse to its previous node in a circular linked list, which is not possible in a singly linked list. (Think!)
Disadvantages of Circular linked list
- If not traversed carefully, then we could end up in an infinite loop because here we don't have any NULL value to stop the traversal.
- Operations in a circular linked list are complex as compared to a singly linked list and doubly linked list like reversing a circular linked list, etc.
Basic Operations on Linked List
- Traversal: To traverse all the nodes one after another.
- Insertion: To add a node at the given position.
- Deletion: To delete a node.
- Searching: To search an element(s) by value.
- Updating: To update a node.
- Sorting: To arrange nodes in a linked list in a specific order.
- Merging: To merge two linked lists into one.
We will see the various implementation of these operations on a singly linked list.
Following is the structure of the node in a linked list:
class Node{ int data // variable containing the data of the node Node next // variable containing the address of next node }Linked List Traversal
The idea here is to step through the list from beginning to end. For example, we may want to print the list or search for a specific node in the list.
The algorithm for traversing a list
- Start with the head of the list. Access the content of the head node if it is not null.
- Then go to the next node(if exists) and access the node information
- Continue until no more nodes (that is, you have reached the null node)
Linked List node Insertion
There can be three cases that will occur when we are inserting a node in a linked list.
- Insertion at the beginning
- Insertion at the end. (Append)
- Insertion after a given node
Insertion at the beginning
Since there is no need to find the end of the list. If the list is empty, we make the new node as the head of the list. Otherwise, we we have to connect the new node to the current head of the list and make the new node, the head of the list.
Insertion at end
We will traverse the list until we find the last node. Then we insert the new node to the end of the list. Note that we have to consider special cases such as list being empty.
In case of a list being empty, we will return the updated head of the linked list because in this case, the inserted node is the first as well as the last node of the linked list.
Insertion after a given node
We are given the reference to a node, and the new node is inserted after the given node.
NOTE: If the address of the prevNode is not given, then you can traverse to that node by finding the data value.
Linked List node Deletion
To delete a node from a linked list, we need to do these steps
- Find the previous node of the node to be deleted.
- Change the next pointer of the previous node
- Free the memory of the deleted node.
In the deletion, there is a special case in which the first node is deleted. In this, we need to update the head of the linked list.
Linked List node Searching
To search any value in the linked list, we can traverse the linked list and compares the value present in the node.
bool searchLL(Node head, int val) { Node temp = head // creating a temp variable pointing to the head of the linked list while( temp != NULL) // traversing the list { if( temp.data == val ) return true temp = temp.next } return false }Linked List node Updation
To update the value of the node, we just need to set the data part to the new value.
Below is the implementation in which we had to update the value of the first node in which data is equal to val and we have to set it to newVal.
void updateLL(Node head, int val, int newVal) { Node temp = head while(temp != NULL) { if( temp.data == val) { temp.data = newVal return } temp = temp.next } }Suggested Problems to solve in Linked List
- Reverse linked list
- Middle of the Linked List
- Odd even linked List
- Remove Duplicates from Sorted List
- Merge Sort on Linked List
- Check if a singly linked list is a palindrome
- Detect and Remove Loop in a Linked List
- Sort a linked list using insertion sort
- Remove Nth Node from List End
Happy coding! Enjoy Algorithms.