Linked List is one of the most important data structures in computer science due to several reasons. The most important one is the drawbacks of the array data structure. Deletion of the elements of the array data structure is highly in-efficient and requires a very time-consuming process. Linked list overcomes this drawback as well as many other drawbacks of the array data structure with the help of concepts such as pointers and references. In this article, we will discuss how to reverse a singly linked list using two approaches.
Reverse Singly Linked List
Given a Singly Linked list containing n number of predefined nodes, the main task is to reverse the linked list without using any other linked lists.
Input: 1->2->3->4->5->null Output: 5->4->3->2->1->null Input: null Output null Input: 2->null Output 2->null
Approach 1: Simple Iterative Approach
This approach is a little tricky. In this approach, we use three-pointers or three references.
- Iterate the original Linked List using for loop or while loop and do the following operations.
- Store the current.next element in one reference or pointer of the node.
- Change the current.next reference/pointer to the second reference.
- Update the second reference/Pointer with the current element.
- Update the current reference/Pointer.
Java:
//Importing Libraries
import java.util.*;
import java.io.*;
class Main{
//Creating head reference of the linked list
static Node head;
//Creating static class of the linked list
static class Node{
int data; //Data to be stored in the node of the linked list
Node next; //Reference of the node in the linked list
//Constructor of the static class
public Node(int data){
this.data=data;
}
}
//Function to insert the node in the linked list
static void push(int data){
if(head==null){
//Insert the head if the linked list is null
head=new Node(data);
}
else{
Node temp=head;
//Iterate the linked list
while(temp.next!=null){
temp=temp.next;
}
temp.next=new Node(data);
}
}
//Function to print the linked list
static void print(Node head){
Node temp=head;
while(temp!=null){
//Printing the data of the node
System.out.print(temp.data+" ");
//Increment the node of the linked list
temp=temp.next;
}
System.out.println();
}
//Function to reverse the linked list
static Node reverse(Node head){
Node current=head;
//Creating two reference
//First reference
Node previous_node=null;
Node previous_previous_node=null;
while(current!=null){
//Store the current.next reference
previous_node=current.next;
//Initialize the current.next last previous node
current.next=previous_previous_node;
//Update the last previous node current element
previous_previous_node=current;
current=previous_node;
}
//Return the reversed Linked list
return previous_previous_node;
}
public static void main(String[] args) {
//Creating Head of the linked list
push(1);
//Creating second node of the linked list
push(2);
//Creating third node of the linked list
push(3);
//Creating fourth node of the linked list
push(4);
//Creating fifth node of the linked list
push(5);
System.out.println("Original Linked List");
print(head);
System.out.println("Reversed Linked List");
Node head_reversed=reverse(head);
print(head_reversed);
}
}
Output:
Python:
#Creating Node class
class Node:
#Creating Constructor
def __init__(self,data):
self.data=data #Creating data to be stored in the node of the linked list
self.next=None #Creating next reference of the node
#Creating class of Linked class
class LinkedList:
#Creating Constructor
def __init__(self):
self.head=None
#Funcion to insert new node in the linked list
def insert(self,data):
#Checking if head is not None
if self.head is None:
self.head=Node(data)
else:
last=self.head
while(last.next):
last=last.next
#Insert last node in the linked list
last.next=Node(data)
#Function to print the Linked list
def print(self):
#Creating temp reference of the head
temp=self.head
LinkedList=[]
#Iterate the Linked list
while(temp is not None):
#Storting the node data in the list
LinkedList.append(temp.data)
temp=temp.next
#Printing the list
print(LinkedList)
#Function to reverse the Linked list
def reverse(self):
#Creating two reference
current=self.head
#First reference
previous=None
#Second reference
previous_previous=None
while(current is not None):
#Store the current.next reference
previous=current.next
#Initialize the current.next last previous node
current.next=previous_previous
#Update the last previous node current element
previous_previous=current
current=previous
self.head=previous_previous
list=LinkedList()
#Inserting First Node in the Linked List
list.insert(1)
#Inserting Second Node in the Linked List
list.insert(2)
#Inserting Third Node in the Linked List
list.insert(3)
print("Original Linked List")
list.print()
list.reverse()
#Printing Reversed Linked List
print("Reversed Linked List")
list.print()
Output:
C++:
//Importing all the required libraries
#include<bits/stdc++.h>
using namespace std;
//Creating structure for the node of linked list
struct Node{
int data;//data to be stored to the node in the linked list
Node*next;//next reference to the node in the linked list
//Creating Constructor
Node(int data){
this->data=data; //Storing the data to the node
this->next=nullptr;
}
};
//Function to Transverse the Linked list
void print(Node *head){
//Checking if the Linked list is null or not
Node *temp=head;
if(temp==NULL){
return;
}
//Transverse the Linked List
while(temp!=NULL){
cout<data<<" "; temp=temp->next;
}
}
//Function reverse the linked list
Node* reverse_LinkedList(Node *head){
//Creating two pointers
Node *current=head;
//First pointer
Node *previous=NULL;
//Second pointer
Node *previous_previous=NULL;
while(current!=NULL){
//Store the current->next reference
previous=current->next;
//Update the last previous node
current->next=previous_previous;
//Update the last previous node
previous_previous=current;
current=previous;
}
head=previous_previous;
//Returning the Reversed Linked list
return head;
}
int main(){
//Creating Head of the linked list
Node *head =new Node(10);
//Creating Second node of the linked list
head->next=new Node(11);
//Creating third node of the linked list
head->next->next=new Node(12);
//Printing Original Linked List
printf("Original Linked List\n");
print(head);
printf("\n");
//Printing Reversed Linked List
printf("Reversed linked list\n");
Node * head1=reverse_LinkedList(head);
print(head1);
return 0;
}
Output:
Complexity:
- Time Complexity : The Time complexity of this approach is O(n).
- Space Complexity : The Space Complexity of this approach is O(1).
Approach 2: (Recursive Approach)
In this approach, we will use recursion to reverse the original linked list.
- Divide the Linked list into two halves, the first node and the remaining nodes of the original list.
- Call recursive function and link the remaining Linked list to the first node of the original linked list.
- At last the change the head Pointer/Reference of the Linked List.
Java
//Importing Libraries
import java.util.*;
import java.io.*;
class Main{
//Creating head reference of the linked list
static Node head;
//Creating static class of the linked list
static class Node{
int data; //Data to be stored in the node of the linked list
Node next; //Reference of the node in the linked list
//Constructor of the static class
public Node(int data){
this.data=data;
}
}
//Function to insert the node in the linked list
static void push(int data){
if(head==null){
//Insert the head if the linked list is null
head=new Node(data);
}
else{
Node temp=head;
//Iterate the linked list
while(temp.next!=null){
temp=temp.next;
}
temp.next=new Node(data);
}
}
//Function to print the linked list
static void print(Node head){
Node temp=head;
while(temp!=null){
//Printing the data of the node
System.out.print(temp.data+" ");
//Increment the node of the linked list
temp=temp.next;
}
System.out.println();
}
//Function to reverse the linked list
static Node reverse(Node head){
//Checking the base condition
if(head==null||head.next==null){
return head;
}
//Recursively call the remaining Linked list
Node small=reverse(head.next);
//Update the head of the Linked List
//Reverse the two nodes
head.next.next=head;
//Update the head pointer/Reference
head.next=null;
return small;
}
public static void main(String[] args) {
//Creating Head of the linked list
push(1);
//Creating second node of the linked list
push(2);
//Creating third node of the linked list
push(3);
//Creating fourth node of the linked list
push(4);
//Creating fifth node of the linked list
push(5);
System.out.println("Original Linked List");
print(head);
System.out.println("Reversed Linked List");
Node head_reversed=reverse(head);
print(head_reversed);
}
}
Output:
C++:
//Importing all the required libraries
#include
#include
#include<bits/stdc++.h>
using namespace std;
//Creating structure for the node of linked list
struct Node{
int data;//data to be stored to the node in the linked list
Node*next;//next reference to the node in the linked list
//Creating Constructor
Node(int data){
this->data=data; //Storing the data to the node
this->next=nullptr;
}
};
//Function to Transverse the Linked list
void print(Node *head){
//Checking if the Linked list is null or not
Node *temp=head;
if(temp==NULL){
return;
}
//Transverse the Linked List
while(temp!=NULL){
cout<data<<" "; temp=temp->next;
}
}
//Function reverse the linked list
Node *reverse_LinkedList(Node *head){
//Checking the base condition
if(head->next==NULL||head==NULL){
return head;
}
//Recursively call the remaining node of the linked list
Node* remaining=reverse_LinkedList(head->next);
//Update the reference of the head pointer
head->next->next=head;
head->next=NULL;
return remaining;
}
int main(){
//Creating Head of the linked list
Node *head =new Node(10);
//Creating Second node of the linked list
head->next=new Node(11);
//Creating third node of the linked list
head->next->next=new Node(12);
//Printing Original Linked List
printf("Original Linked List\n");
print(head);
printf("\n");
//Printing Reversed Linked List
printf("Reversed linked list\n");
Node * head1=reverse_LinkedList(head);
print(head1);
return 0;
}
Output:
Python:
#Creating Node class
class Node:
def __init__(self,data):
self.data=data #Creating data of the node
self.next=None #Creating next reference of the node of the linked list
#Creating Linked List
class LinkedList:
#Creating Linked List class constructor
def __init__(self):
self.head=None
#Function to push the node in the linked list
def push(self,data):
node=Node(data)
node.next=self.head
self.head=node #Update the head pointer
#Function to reverse the Linked list
def reverse(self,head):
#Checking the head of the linked list
if head is None or head.next is None:
return head
#Recursively call the remaining node of the linked list
remaining=self.reverse(head.next)
#Update the head reference in the linked list
head.next.next=head
head.next=None
#Return the Reversed Linked List
return remaining
#Function to print the LinkedList
def printList(self):
temporary_List=self.head
List=[]
#Iterate the Linked List
while(temporary_List):
#Add the node value to the list
List.append(temporary_List.data)
temporary_List=temporary_List.next
#Print the List
print(List)
#Creating List reference of the Linked List
List=LinkedList()
#Inserting node in the Single list
List.push(1)
List.push(2)
List.push(3)
#Printing the original linked list
print("Original Linked List")
List.printList()
#Printing the reversed Linked List
print("Reversed Linked List")
List.head=List.reverse(List.head)
List.printList()
Output:
Conclusion
Reversing a Linked List is one of the most interesting problems of Data structure. In this article, we have discussed two approaches to Reverse a linked list. One approach is using a simple iteration with three-pointers/reference concepts and a second approach is a recursive approach. There are so many interesting projects that can be easily made using the concept of Reversing a Linked list and the most common example is Snake Game .
We hope this article will help you to understand the problem statement and you will be able to solve any other variation of this problem.
Happy Coding!
People are also reading:
- Maximum size square sub-matrices with all 1’s
- Merge Sort for Linked Lists
- Convert a Binary Tree to Doubly Linked List
- Minimum Edit Distance
- WAP to Print Square Using * Character
- Rearrange an array in maximum minimum form
- Print a given matrix in spiral form
- Sort binary array in linear time
- Write a Program to read from a text file and then write in another text file
- Move all zeros present in an array to the end
Leave a Comment on this Post