Posted in

Vinay Khatri
Last updated on June 10, 2022

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.

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 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){
}
else{

while(temp.next!=null){
temp=temp.next;
}
temp.next=new Node(data);
}
}
//Function to print the linked list
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
//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 previous_previous_node;
}
public static void main(String[] args) {
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);
}
}
```

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 Constructor
def __init__(self):
#Funcion to insert new node in the linked list
def insert(self,data):
#Checking if head is not None
else:
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
while(temp is not None):
#Storting the node data in the list
temp=temp.next
#Printing the list
#Function to  reverse the Linked list
def reverse(self):
#Creating two reference

#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
#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)
list.print()

list.reverse()
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
//Checking if the Linked list is null or not
if(temp==NULL){
return;
}
while(temp!=NULL){
cout<data<<" "; temp=temp->next;
}

}
//Creating two pointers
//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;
}

}

int main(){
//Creating Second node of the linked list
//Creating third node of the linked list

printf("\n");

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 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){
}
else{

while(temp.next!=null){
temp=temp.next;
}
temp.next=new Node(data);
}
}
//Function to print the linked list
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
//Checking the base condition
}
//Recursively call the remaining Linked list
//Reverse the two nodes
return small;
}
public static void main(String[] args) {
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);
}
}
```

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
//Checking if the Linked list is null or not
if(temp==NULL){
return;
}
while(temp!=NULL){
cout<data<<" "; temp=temp->next;
}

}
//Checking the base condition
}
//Recursively call the remaining node of the linked list
//Update the reference of the head pointer
return remaining;
}

int main(){
//Creating Second node of the linked list
//Creating third node of the linked list

printf("\n");

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
def __init__(self):
#Function to push the node in the linked list
def push(self,data):
node=Node(data)
#Function to reverse the Linked list
#Recursively call the  remaining node of the linked list
return remaining
def printList(self):
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
#Inserting node in the Single list
List.push(1)
List.push(2)
List.push(3)
List.printList()
List.printList()```

Output: