Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
Reversing a linked list is a common problem in data structures where the order of nodes is reversed, making the last node the new head. This can be achieved using iterative or recursive methods, and mastering it enhances understanding of pointers and node manipulation in linked lists.
In this article, we’ll learn how to reverse a linked list, a fundamental technique in data structures that involves reversing the order of nodes so that the last node becomes the head. We’ll cover both iterative and recursive methods, which help deepen understanding of pointers and linked list manipulation.
The ‘HEAD’ pointer of a linked list is given. Return the ‘HEAD’ pointer of the reversed linked list.
Input
Enter the number of nodes in the linked list: 4
Enter the data of nodes: 1 2 3 4
Output
Reversed linked list: 4 3 2 1
Explanation
Recommended: Try the Problem yourself before moving on to the Solution
Approach1: Using Stack
Stack follows the LIFO principle, which means the element that comes at the last should be shown first. That’s exactly what we want. We want to print the last node of the linked list first and so on.
Using stack to create a reversed linked list is pretty simple. Put all the nodes of the linked list in a stack.
Then, start popping out the nodes from the stack. Set the ‘NEXT’ pointer of the current popped node to the previously popped node.
Refer to the algorithm given below for a better understanding.
void printLinkedList() { Node* current = head; while (current) { cout << current->data << " "; current = current->next; } cout << endl; }
void insert(int data) { if (head == NULL) { head = new Node(data); return; } Node* current = head; while (current->next) { current = current->next; } current->next = new Node(data); }
void reverseLinkedList() { stack<Node*> nodeStack; Node* current = head; while (current->next) { nodeStack.push(current); current = current->next; } head = current; Node* previousTop = current; while (!nodeStack.empty()) { current = nodeStack.top(); nodeStack.pop(); previousTop->next = current; previousTop = current; } previousTop->next = NULL; printLinkedList(); } };
int main() { int totalNodes; cout << "Enter the number of nodes in the linked list: "; cin >> totalNodes;
cout << "Enter the data of nodes: "; LinkedList* givenList = new LinkedList(); for (int i = 0; i < totalNodes; i++) { int data; cin >> data; givenList->insert(data); }
class Node: def __init__(self, data): self.data = data self.next = None
class LinkedList: def __init__(self): self.head = None
def insert(self, data): new_node = Node(data) if not self.head: self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node
def reverse_linked_list(self): stack = [] current = self.head while current.next: stack.append(current) current = current.next self.head = current previous_top = current while stack: current = stack.pop() previous_top.next = current previous_top = current previous_top.next = None self.print_linked_list()
def print_linked_list(self): current = self.head while current: print(current.data, end=" ") current = current.next print()
# Driver code if __name__ == "__main__": linked_list = LinkedList() total_nodes = int(input("Enter the number of nodes: ")) print("Enter node data:") for _ in range(total_nodes): data = int(input()) linked_list.insert(data) print("Reversed linked list: ", end="") linked_list.reverse_linked_list()
You can also try this code with Online Python Compiler
public void Insert(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; return; } Node current = head; while (current.next != null) { current = current.next; } current.next = newNode; }
public void ReverseLinkedList() { Stack<Node> stack = new Stack<Node>(); Node current = head; while (current.next != null) { stack.Push(current); current = current.next; } head = current; Node previousTop = current; while (stack.Count > 0) { current = stack.Pop(); previousTop.next = current; previousTop = current; } previousTop.next = null; PrintLinkedList(); }
public void PrintLinkedList() { Node current = head; while (current != null) { Console.Write(current.data + " "); current = current.next; } Console.WriteLine(); }
static void Main() { Console.Write("Enter the number of nodes: "); int totalNodes = int.Parse(Console.ReadLine()); LinkedList linkedList = new LinkedList();
Console.WriteLine("Enter node data:"); for (int i = 0; i < totalNodes; i++) { int data = int.Parse(Console.ReadLine()); linkedList.Insert(data); }
class LinkedList { constructor() { this.head = null; }
insert(data) { let newNode = new Node(data); if (!this.head) { this.head = newNode; return; } let current = this.head; while (current.next) { current = current.next; } current.next = newNode; }
reverseLinkedList() { let stack = []; let current = this.head; while (current.next) { stack.push(current); current = current.next; } this.head = current; let previousTop = current; while (stack.length > 0) { current = stack.pop(); previousTop.next = current; previousTop = current; } previousTop.next = null; this.printLinkedList(); }
printLinkedList() { let current = this.head; let result = []; while (current) { result.push(current.data); current = current.next; } console.log(result.join(" ")); } }
// Driver code const linkedList = new LinkedList(); const totalNodes = parseInt(prompt("Enter the number of nodes: ")); for (let i = 0; i < totalNodes; i++) { const data = parseInt(prompt("Enter node data:")); linkedList.insert(data); } console.log("Reversed linked list:"); linkedList.reverseLinkedList();
You can also try this code with Online Javascript Compiler
Enter the number of nodes in the linked list: 6
Enter the data of nodes: 1 2 3 6 5 4
Output
Reversed linked list: 4 5 6 3 2 1
Complexity Analysis
Time Complexity: Traversal through the linked list is required to store the nodes of the linked list in the stack. Similarly, the linked list nodes are popped off the stack one by one until the stack is empty. Both these operations are linear-time operations. So, the time complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.
Space Complexity: Additional space is required to store the nodes of the linked list in the stack. The space required is linearly proportional to the size of the linked list. So, the space complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.
Approach 2: Using Iteration with constant space
In the previous method, we first traversed through the linked list to store all the nodes. If you notice, we only need two nodes at a time for reversal: ‘PREVIOUS_TOP’ and ‘CURRENT’ to reverse the pointer of one node at a time.
Rather than start reversing the linked list from end, we can start the reversal from the Rather than start reversing the linked list from the end, we can start the reversal from the beginning.
The problem we’ll face here is that if we redirect the ‘NEXT’ pointer of ‘NODE_2’, the linked list is split into two parts. This makes moving to the ‘NEXT’ node impossible. Refer to the figure given below for the illustration of the same.
The solution for this problem is to add a pointer ‘NEXT_TO_CURRENT’ pointer to store the address of the pointer ‘NEXT’ to current.
After setting the pointer of the ‘NEXT’ node, we can make the ‘PREVIOUS_TOP’ node our ‘CURRENT ’node and move the ‘CURRENT’ node to the next node.
These actions are repeated until the linked list is completely traversed. In the end, the ‘PREVIOUS_TOP’ points to the last node of the linked list. As the last node of a linked list becomes the first node when the linked list is reversed, we consider ‘PREVIOUS_TOP’ to be the ‘HEAD’ of the newly created linked list. Refer to the algorithm given below for a better understanding.
Algorithm
Set the ‘CURRENT’ equal to ‘HEAD’.
Set the ‘PREVIOUS_TOP’ equal to NULL(First element of the linked list should point to NULL after reversal).
Declare ‘NEXT_TO_CURRENT’ node pointer.
While ‘CURRENT’ is not equal to NULL, do:
Set NEXT_TO_CURRENT = CURRENT -> NEXT.
Set CURRENT -> NEXT = PREVIOUS_TOP.
Set PREVIOUS_TOP = CURRENT.
Set CURRENT = NEXT.
Set HEAD = PREVIOUS_TOP.
Implementation
C++
C
Java
Python
JavaScript
C#
C++
#include <iostream> using namespace std;
// 'NODE' class to store linked list nodes. class Node {
public: int data; Node *next;
// Constructor to create a node with given data. Node(int data) { this->data = data; next = NULL; } };
// 'LINKED_LIST' class to create linked list objects. class LinkedList {
// 'HEAD' node to store the address of the first node. Node *head;
public: LinkedList() { head = NULL; }
// Function to print the linked list elements. void printLinkedList() {
/* 'CURRENT' node pointer traverses through the linked list. Set 'CURRENT' node equal to first node of the linked list. */ Node *current = head;
// Loop to traverse the linked list. while (current) { cout << current->data << " "; current = current->next; } cout << endl; }
// Function to insert nodes in the linked list. void insert(int data) {
/* If linked list is empty, create a new node and direct the 'HEAD' node to the newly created node. */ if (head == NULL) { head = new Node(data); return; }
// Else traverse the linked list until end of the list is encountered. Node *current = head; while (current->next) { current = current->next; }
// Create and insert a new node at the end of the linked list. current->next = new Node(data); }
void reverseLinkedList() {
// Set 'CURRENT' node equal to the first node of the linked list. Node *current = head;
// Initialise 'PREVIOUS_TOP' as NULL to store the previous top element. Node *previousTop = NULL;
// Traverse through the linked list and redirecting the pointers to the previous elements. while (current) {
// Initialise 'NEXT_TO_CURRENT' node pointer with CURRENT -> NEXT. Node *nextToCurrent = current->next;
// Redirect 'NEXT' pointer of the 'CURRENT' node. current->next = previousTop;
// Move pointers to the next node of linked list. previousTop = current; current = nextToCurrent; }
// Point 'HEAD' equal to the last node of the linked list. head = previousTop;
// Print the reversed linked list. printLinkedList(); } };
int main() { int totalNodes; cout << "Enter the number of nodes in the linked list: "; cin >> totalNodes;
cout << "Enter the data of nodes: "; LinkedList *givenList = new LinkedList(); for (int i = 0; i < totalNodes; i++) { int data; cin >> data; givenList->insert(data); } cout << "Reversed linked list: "; givenList->reverseLinkedList(); }
You can also try this code with Online C++ Compiler
public void insert(int data) { if (head == null) { head = new Node(data); } else { Node current = head; while (current.next != null) { current = current.next; } current.next = new Node(data); } }
public void reverseLinkedList() { Node current = head; Node previousTop = null;
while (current != null) { Node nextToCurrent = current.next; current.next = previousTop; previousTop = current; current = nextToCurrent; } head = previousTop; }
public void printLinkedList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } }
public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); LinkedList linkedList = new LinkedList();
System.out.print("Enter the number of nodes in the linked list: "); int totalNodes = scanner.nextInt();
System.out.println("Enter the data of nodes: "); for (int i = 0; i < totalNodes; i++) { int data = scanner.nextInt(); linkedList.insert(data); }
class Node: def __init__(self, data): self.data = data self.next = None
class LinkedList: def __init__(self): self.head = None
def insert(self, data): if not self.head: self.head = Node(data) else: current = self.head while current.next: current = current.next current.next = Node(data)
def reverse_linked_list(self): current = self.head previous_top = None
while current: next_to_current = current.next current.next = previous_top previous_top = current current = next_to_current
self.head = previous_top
def print_linked_list(self): current = self.head while current: print(current.data, end=" ") print()
if __name__ == "__main__": linked_list = LinkedList() total_nodes = int(input("Enter the number of nodes in the linked list: "))
print("Enter the data of nodes: ") for _ in range(total_nodes): data = int(input()) linked_list.insert(data)
class LinkedList { constructor() { this.head = null; }
insert(data) { const newNode = new Node(data); if (this.head === null) { this.head = newNode; } else { let current = this.head; while (current.next !== null) { current = current.next; } current.next = newNode; } }
reverseLinkedList() { let current = this.head; let previousTop = null;
while (current !== null) { let nextToCurrent = current.next; current.next = previousTop; previousTop = current; current = nextToCurrent; } this.head = previousTop; }
printLinkedList() { let current = this.head; const result = []; while (current !== null) { result.push(current.data); current = current.next; } console.log(result.join(" ")); } }
const linkedList = new LinkedList(); const totalNodes = parseInt(prompt("Enter the number of nodes in the linked list:")); console.log("Enter the data of nodes: "); for (let i = 0; i < totalNodes; i++) { const data = parseInt(prompt("Enter node data:")); linkedList.insert(data); }
public void Insert(int data) { if (head == null) { head = new Node(data); } else { Node current = head; while (current.next != null) { current = current.next; } current.next = new Node(data); } }
public void ReverseLinkedList() { Node current = head; Node previousTop = null;
while (current != null) { Node nextToCurrent = current.next; current.next = previousTop; previousTop = current; current = nextToCurrent; }
head = previousTop; }
public void PrintLinkedList() { Node current = head; while (current != null) { Console.Write(current.data + " "); current = current.next; } Console.WriteLine(); } }
class Program { static void Main(string[] args) { LinkedList linkedList = new LinkedList();
Console.Write("Enter the number of nodes in the linked list: "); int totalNodes = int.Parse(Console.ReadLine());
Console.WriteLine("Enter the data of nodes: "); for (int i = 0; i < totalNodes; i++) { int data = int.Parse(Console.ReadLine()); linkedList.Insert(data); }
Enter the number of nodes in the linked list: 5
Enter the data of nodes: 10 32 20 11 2
Output
Reversed linked list: 2 11 20 32 10
Complexity Analysis
Time Complexity: Traversal through the linked list is required to reverse the pointers of the linked list nodes. Traversal through the linked list is a linear-time operation. So, the time complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.
Space Complexity: Constant space is required to store the ‘PREVIOUS_TOP’, ‘CURRENT’, and ‘NEXT_TO_CURRENT’ pointers. So, the space complexity of the method is O(1).
The operations discussed above can also be achieved using recursion. The ‘PREVIOUS_TOP’, ‘CURRENT’, and ‘HEAD’ pointers are fed to the recursive functions as the function parameters.
The base function of the recursive function is to check whether the ‘NEXT’ pointer to the ‘CURRENT’ node exists. If no ‘NEXT’ pointer exists, that means we have encountered the last node of the list. So, the last node of the linked list should be stored as the head of the reversed linked list.
Like the iterative solution, we set the ‘NEXT’ node of the ‘CURRENT’ node into a variable ‘NEXT_TO_CURRENT’. The ‘NEXT’ pointer of the ‘CURRENT’ node is redirected to the ‘PREVIOUS_TOP’. After redirection, ’PREVIOUS_TOP’ is set to ‘CURRENT’, and the ‘CURRENT’ is set to ‘NEXT_TO_CURRENT’. The recursive function will be called using the new parameters. Refer to the given algorithm for a better understanding.
Algorithm
If CURRENT -> NEXT is equal to NULL, then:
Set ‘HEAD’ = ‘CURRENT’.
Set CURRENT -> NEXT = PREVIOUS_TOP.
Return
Set NEXT_TO_CURRENT = CURRENT -> NEXT.
Set CURRENT -> NEXT = PREVIOUS_TOP.
Call the recursive function with ‘NEXT_TO_CURRENT’ and ‘CURRENT parameters.
Implementation
C++
C
Java
Python
C#
JavaScript
C++
#include <iostream> using namespace std;
// 'NODE' class to store linked list nodes. class Node {
public: int data; Node *next;
// Constructor to create a node with given data. Node(int data) { this->data = data; next = NULL; } };
// 'LINKED_LIST' class to create linked list objects. class LinkedList {
// 'HEAD' node to store the address of the first node. Node *head;
public: LinkedList() { head = NULL; }
// Function to print the linked list elements. void printLinkedList() {
/* 'CURRENT' node pointer traverses through the linked list. Set 'CURRENT' node equal to first node of the linked list. */ Node *current = head;
// Loop to traverse the linked list. while (current) { cout << current->data << " "; current = current->next; } cout << endl; }
// Function to insert nodes in the linked list. void insert(int data) {
/* If linked list is empty, create a new node and direct the 'HEAD' node to the newly created node. */ if (head == NULL) { head = new Node(data); return; }
// Else traverse the linked list until end of the list is encountered. Node *current = head; while (current->next) { current = current->next; }
// Create and insert a new node at the end of the linked list. current->next = new Node(data); }
/* Last node of the linked list. Point 'HEAD' to this node. */ if (!current->next) { head = current; current->next = previousTop; return; }
// Initialize 'NEXT_TO_CURRENT' pointer with CURRENT->NEXT. Node *nextToCurrent = current->next;
// Redirect 'NEXT' pointer of the 'CURRENT' node. current->next = previousTop;
// Call the recursive function with 'NEXT_TO_CURRENT' and 'CURRENT' parameters. reverseLinkedListHelper(nextToCurrent, current); }
void reverseLinkedList() {
// If 'HEAD' is not pointing to any node, list is empty. if (!head) return;
// Set 'CURRENT' node equal to first node of the linked list. Node *current = head;
/* Set 'PREVIOUS_TOP' node to NULL to represent end of the linked list after reversal. */ Node *previousTop = NULL;
// Call helper function to reverse the linked list. reverseLinkedListHelper(current, previousTop);
// Print the reversed linked list. printLinkedList(); } };
int main() { int totalNodes; cout << "Enter the number of nodes in the linked list: "; cin >> totalNodes;
cout << "Enter the data of nodes: "; LinkedList *givenList = new LinkedList(); for (int i = 0; i < totalNodes; i++) { int data; cin >> data; givenList->insert(data); } cout << "Reversed linked list: "; givenList->reverseLinkedList(); }
You can also try this code with Online C++ Compiler
public void insert(int data) { if (head == null) { head = new Node(data); return; } Node current = head; while (current.next != null) { current = current.next; } current.next = new Node(data); }
public void printLinkedList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); }
public Node reverseLinkedList(Node node) { Node prev = null; Node current = node; Node next; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } head = prev; return head; }
public static void main(String[] args) { LinkedList list = new LinkedList(); list.insert(1); list.insert(2); list.insert(3); System.out.println("Original List:"); list.printLinkedList(); System.out.println("Reversed List:"); list.reverseLinkedList(list.head); list.printLinkedList(); } }
You can also try this code with Online Java Compiler
class Node: def __init__(self, data): self.data = data self.next = None
class LinkedList: def __init__(self): self.head = None
def insert(self, data): if self.head is None: self.head = Node(data) return current = self.head while current.next: current = current.next current.next = Node(data)
def print_linked_list(self): current = self.head while current: print(current.data, end=" ") current = current.next print()
def reverse_linked_list(self): prev = None current = self.head while current: next_node = current.next current.next = prev prev = current current = next_node self.head = prev
public void Insert(int data) { if (head == null) { head = new Node(data); return; } Node current = head; while (current.next != null) { current = current.next; } current.next = new Node(data); }
public void PrintLinkedList() { Node current = head; while (current != null) { Console.Write(current.data + " "); current = current.next; } Console.WriteLine(); }
public void ReverseLinkedList() { Node prev = null; Node current = head; Node next = null; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } head = prev; } }
class Program { static void Main() { LinkedList list = new LinkedList(); list.Insert(1); list.Insert(2); list.Insert(3); Console.WriteLine("Original List:"); list.PrintLinkedList(); list.ReverseLinkedList(); Console.WriteLine("Reversed List:"); list.PrintLinkedList(); } }
class LinkedList { constructor() { this.head = null; }
insert(data) { if (this.head === null) { this.head = new Node(data); return; } let current = this.head; while (current.next !== null) { current = current.next; } current.next = new Node(data); }
printLinkedList() { let current = this.head; let result = ""; while (current) { result += current.data + " "; current = current.next; } console.log(result.trim()); }
reverseLinkedList() { let prev = null; let current = this.head; let next = null; while (current) { next = current.next; current.next = prev; prev = current; current = next; } this.head = prev; } }
// Example usage: let list = new LinkedList(); list.insert(1); list.insert(2); list.insert(3); console.log("Original List:"); list.printLinkedList(); list.reverseLinkedList(); console.log("Reversed List:"); list.printLinkedList();
You can also try this code with Online Javascript Compiler
Enter the number of nodes in the linked list: 4
Enter the data of nodes: 1 2 3 4
Output
Reversed linked list: 4 3 2 1
Complexity Analysis
Time Complexity: Traversal through the linked list is required to reverse the pointers of the linked list nodes. Traversal through the linked list is a linear-time operation. So, the time complexity of this method is O(N), where ‘N’ represents the number of nodes in the linked list.
Space Complexity: The recursion stack space requires O(N) space.
Skimming through blogs can be perplexing at times, so let's watch a video to quickly learn how to reverse a Linked List - Iteratively & Recursively.
Frequently Asked Question
What are the main steps involved in reversing a singly linked list?
To reverse a singly linked list, initialize three pointers: prev, current, and next. Traverse the list, setting each node’s next pointer to prev, updating prev and current sequentially until the list is fully reversed.
How many pointers are required to reverse a linked list?
Reversing a singly linked list typically requires three pointers: prev, current, and next. The prev pointer tracks the reversed part, current points to the node being processed, and next temporarily holds the next node in the original sequence.
How can reversing a linked list affect its usability or performance in an application?
Reversing a linked list can improve access to the last node but may slow down applications requiring the original order. It also changes node traversal direction, potentially impacting algorithms that depend on sequential data access.
Why do we need to reverse a linked list?
The node’s next property determines the order in a singly linked list. This could either refer to another node or point to null if it is the last node in the list. Reversing a linked list, therefore, refers to reassigning all the next properties on every node.
Conclusion
Reversing a linked list may look like a simple operation. However, the applications of linked list reversal are vast. Many algorithms related to linked lists are based on the linked list reversal.