Apply Now
Problems

Reverse a Linked List

By Venkatesan Prabu
January 3, 2024 3 Min Read
162 0

Reverse a Linked List

Problem Statement

Given a singly linked list, the task is to reverse the list, meaning that the last node becomes the first node, the second-to-last node becomes the second node, and so on.

Table Of Content

Recursive Approach

The recursive approach to reversing a linked list involves breaking the problem into smaller subproblems. Here are the general steps:

  • Divide the linked list into two parts: the first node (head) and the rest of the list (the linked list without the first node).
  • Recursively reverse the rest of the linked list.
  • After the recursion, change the next of the last node of the reversed rest to point to the first node.
  • Set the next of the first node to NULL to make it the new tail.

Implementation of Recursive Approach

C++ Implementation

#include <iostream>

class Node {

public:

int data;

Node* next;

Node(int data) : data(data), next(nullptr) {}

};

Node* reverseLinkedList(Node* head) {

if (head == nullptr || head->next == nullptr) {

return head;

}

Node* restReversed = reverseLinkedList(head->next);

head->next->next = head;

head->next = nullptr;

return restReversed;

}

void printLinkedList(Node* head) {

while (head != nullptr) {

std::cout << head->data << " ";

head = head->next;

}

std::cout << std::endl;

}

int main() {

Node* head = new Node(1);

head->next = new Node(2);

head->next->next = new Node(3);

head->next->next->next = new Node(4);

std::cout << "Original Linked List: ";

printLinkedList(head);

head = reverseLinkedList(head);

std::cout << "Reversed Linked List: ";

printLinkedList(head);

return 0;

}

Java Implementation

class Node {

int data;

Node next;

Node(int data) {

this.data = data;

this.next = null;

}

}

public class ReverseLinkedList {

public static Node reverseLinkedList(Node head) {

if (head == null || head.next == null) {

return head;

}

Node restReversed = reverseLinkedList(head.next);

head.next.next = head;

head.next = null;

return restReversed;

}

public static void printLinkedList(Node head) {

while (head != null) {

System.out.print(head.data + " ");

head = head.next;

}

System.out.println();

}

public static void main(String[] args) {

Node head = new Node(1);

head.next = new Node(2);

head.next.next = new Node(3);

head.next.next.next = new Node(4);

System.out.print("Original Linked List: ");

printLinkedList(head);

head = reverseLinkedList(head);

System.out.print("Reversed Linked List: ");

printLinkedList(head);

}

}

Python Implementation

class ListNode:

def __init__(self, data):

self.data = data

self.next = None

def reverseLinkedList(head):

if head is None or head.next is None:

return head

restReversed = reverseLinkedList(head.next)

head.next.next = head

head.next = None

return restReversed

def printLinkedList(head):

while head:

print(head.data, end=" ")

head = head.next

print()

# Helper function to create a linked list from a list

def createLinkedList(arr):

if not arr:

return None

head = ListNode(arr[0])

current = head

for item in arr[1:]:

current.next = ListNode(item)

current = current.next

return head

# Helper function to print a linked list

def printLinkedList(head):

while head:

print(head.data, end=" ")

head = head.next

print()

if __name__ == "__main__":

arr = [1, 2, 3, 4]

head = createLinkedList(arr)

print("Original Linked List:", end=" ")

printLinkedList(head)

head = reverseLinkedList(head)

print("Reversed Linked List:", end=" ")

printLinkedList(head)

Iterative Approach

The iterative approach to reversing a linked list involves traversing the list once and modifying the next pointers of each node to reverse the direction of the list.

Dry Run of the Iterative Approach

Let’s dry run the iterative approach on a simple example:

Original Linked List: 1 -> 2 -> 3 -> 4 -> null

  1. Initialize three pointers: prev = null, current = head (1st node), and next = null.
  2. Iterate through the linked list.
    • In each iteration, update the next pointer of the current node to point to the previous node (reverse the link).
  • Update prev to be the current node.
  • Update current to be the next node (move forward).
  1. After the loop, update the head to be prev, which is now pointing to the new first node (4).
  2. The reversed linked list is now: 4 -> 3 -> 2 -> 1 -> null.

Implementation of Iterative Approach

C++ Implementation

#include <iostream>

class Node {

public:

int data;

Node* next;

Node(int data) : data(data), next(nullptr) {}

};

Node* reverseLinkedList(Node* head) {

Node* prev = nullptr;

Node* current = head;

Node* next = nullptr;

while (current != nullptr) {

next = current->next;

current->next = prev;

prev = current;

current = next;

}

return prev; // New head of the reversed list

}

void printLinkedList(Node* head) {

while (head != nullptr) {

std::cout << head->data << " ";

head = head->next;

}

std::cout << std::endl;

}

int main() {

Node* head = new Node(1);

head->next = new Node(2);

head->next->next = new Node(3);

head->next->next->next = new Node(4);

std::cout << "Original Linked List: ";

printLinkedList(head);

head = reverseLinkedList(head);

std::cout << "Reversed Linked List: ";

printLinkedList(head);

return 0;

}

Java Implementation

class Node {

int data;

Node next;

Node(int data) {

this.data = data;

this.next = null;

}

}

public class ReverseLinkedList {

public static Node reverseLinkedList(Node head) {

Node prev = null;

Node current = head;

Node next = null;

while (current != null) {

next = current.next;

current.next = prev;

prev = current;

current = next;

}

return prev; // New head of the reversed list

}

public static void printLinkedList(Node head)

FAQs

1.What is a linked list?

A linked list is a linear data structure consisting of nodes, where each node points to the next node in the sequence. It’s used to store and manage a collection of elements.

2.Why would you want to reverse a linked list?

Reversing a linked list can be useful in various scenarios, such as when you need to process elements in a different order, search for elements from the end, or improve the efficiency of certain operations.

3.What is the difference between reversing a linked list iteratively and recursively?

The iterative approach reverses the linked list by iteratively modifying the next pointers of each node to change the direction of the list. The recursive approach divides the problem into smaller subproblems, recursively reverses the rest of the list, and then combines the results.

4.Is there a preferred approach (iterative vs. recursive) for reversing a linked list?

The choice between the iterative and recursive approaches often depends on personal preference and the specific requirements of the problem. Both approaches are valid and can achieve the same result.

5.What is the time complexity of reversing a linked list?

Both the iterative and recursive approaches have a time complexity of O(n), where n is the number of nodes in the linked list. This is because they visit each node once.

Tags:

Share Article

Author

Venkatesan Prabu

An accomplished tech entrepreneur and educator, widely recognized for over a decade of leadership in Microsoft technologies, prestigious MVP accolades, and a deep commitment to student empowerment through hands-on training, internships, and career-focused mentoring. I have published numerous blogs and technical articles, especially in areas like Artificial Intelligence, to bridge the gap between industry practices and academic learning.

Follow Me
Other Articles
No Comment! Be the first one.

Leave a Reply

Your email address will not be published. Required fields are marked *

KaaShiv InfoTech – 2026, All rights reserved.

KaaShiv InfoTech
Courses in Chennai
Internship in Chennai
Inplant Training in Chennai
Training in Chennai
KaaShiv InfoTech
Courses in Chennai
Internship in Chennai
Inplant Training in Chennai
Training in Chennai
Scroll

Our site uses cookies. By using this site, you agree to the Privacy Policy and Terms of Use.

Accept