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.

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 :

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.