Reverse a Linked List

Problem Statement

The objective is to reverse a given linked list, which involves altering the pointers between nodes such that the last node becomes the new head node, and each subsequent node points to its predecessor.

For Example:

Input1 :

Output1 :

Input2 :

Output2 :

Input3 :

Output3 :

Approach 1 : Iterative Method

First, that is the iterative approach to reverse a linked list is given below.

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Algorithm

1. Initialize three-pointers that are curr, prev, and next with NULL values.
2. Go through the linked list iteratively.
   Perform the following in a loop :

Code Implementation

• In C++

• In Java

• In Python

Output :

Complexity Analysis

Time Complexity :
As we will iterate over the whole linked list of size "n" so the time complexity of this approach will be $O(n)$.

Space Complexity :
As no extra memory is being used in this approach so auxiliary space consumed will be $O(1)$.

Approach 2 : Recursive Method

Second, that is a recursive approach to reverse a linked list is given below.

Algorithm

1. The first node and the remainder of the linked list should be separated into two parts.
2. For the remaining linked list items, call reverse.
3. Link the rest to the first.
4. Fix the head pointer.

Code Implementation

• In C++

• In Java

• In Python

Output :

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Complexity Analysis

Time Complexity :
As we are iterating over the linked list with "n" nodes to reverse it then time complexity will be $O(n)$.

Space Complexity :
As we are using extra "n" size space for performing this approach thus it will consume $O(n)$ auxiliary space.

Approach 3 : Tail Recursive Method

As in the previous two approaches we have used the iterative and recursive methods now here we will use this tail recursive method to reverse a linked list.

Code Implementation

• In C++

• In Java

• In Python

Output :

Complexity Analysis

Time Complexity :
As we are iterating over the linked list of size "n" for reversing it, so time complexity will be $O(n)$.

Space Complexity :
As no extra space is required in this approach so it will take $O(1)$ auxiliary space.

Approach 4: Using Stack

Algorithm

1. Store the values in the stack until all the values are entered.
2. Update a Head pointer to a final location(last node) once all entries have been made.
3. Until the stack is empty, begin popping up the nodes and storing them in the same order.
4. Update the last Node’s next pointer in the stack with NULL.

Code Implementation

• In C++

• In Java

• In Python

Output :

Complexity Analysis

Time Complexity :
As we are iterating over the linked list of size "n" for reversing it so time complexity will be $O(n)$.

Space Complexity :
As we are creating a stack and storing "n" nodes values in it. Here "n" is the size of the linked list. So $O(n)$ auxiliary space is used here.