Back to home  Logicmojo - Updated Jan 2, 2023

Problem Statement

Given a pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.

Example:
Input: [1,2,3,4,5,NULL]
Output: [5,4,3,2,1,NULL]

There can be two approaches to solve this problem, the following are the hints, try solving the problem by yourself and then head over to the next section to find the solution and code.

💡 Hints
Think of an iterative approach to find the reversed list in a single pass.
Or, think of a recursive approach to find the reversed list in a single pass.

### Iterative Solution for Reversing a Linked List

If the linked list has only one or no element, then we return the current list as it is. And if there are two or more elements, then we can implement an iterative solution using three-pointers. We will create a function to reverse the linked list taking reference to the head node and as the only argument and return the head of the new linked list:

We will use 3 variables: prevNode, head, and nextNode.

prevNode to NULL
nextNode can stay empty;

Then we will continue our loop until our current maidenhead pointer is truthy (ie: not NULL), which implies that we reached the end of the linked list

During our loop, we first of all update nextNode so that it acquires its namesake value, as head->next.

Finally, we update the head with the value we stored in nextNode.

And finally, we go on with the loop until we can. After the loop, we return prevNode. Implementation of Iterative Approach

Implementation in C++

```#include<bits/stdc++.h>

using namespace std;

struct node {
int data;
struct node *next;
};

// To create a demo we have to construct a linked list and this
// function is to push the elements to the list.
void push(struct node **head_ref, int data) {
struct node *node;
node = (struct node*)malloc(sizeof(struct node));
node->data = data;
}

// Function to reverse the list
struct node *temp = NULL;
struct node *prev = NULL;
while(current != NULL) {
temp = current->next;
current->next = prev;
prev = current;
current = temp;
}
}

// To check our program
}
}

// Driver function
int main() {
cout << "Linked List Before Reversing" << endl;
cout << endl;
cout << "Linked List After Reversing"<<endl;
return 0;
}
```

Implementation in Python

```class Node:
def __init__(self, val):
self.val = val
self.next = None

while ptr:
print(ptr.val, end = '->')
ptr = ptr.next
print('X')

while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt

if __name__=='__main__':

```

Recursive solution for Reversing a Linked List

The most important thing to remember in this approach is that the recursive approach uses a stack. The compiler allocates stack memory after each recursive call, and this solution can run out of memory in case of very huge linked lists (think billions of elements).

We can divide the linked list with n nodes into two parts: head and the rest of the linked list with n-1 nodes (Smaller problem).

Recursively reverse the linked list with (n-1) nodes and return the head pointer of this part i.e. restReversedPart. After the reversal, the next node of the head will be the last node and the head will be pointing to this node.

But for the complete reversal of the list, the head should be the last node. So, do the following operations to ensure this:

Return the head pointer of the reversed list i.e. return restReversedPart. Implementation in C++

```// Recursive C++ program to reverse
#include <iostream>
using namespace std;

struct Node {
int data;
struct Node* next;
Node(int data)
{
this->data = data;
next = NULL;
}
};

{
}

/* Function to reverse the linked list */
Node* reverse(Node* node)
{
if (node == NULL)
return NULL;
if (node->next == NULL) {
return node;
}
Node* node1 = reverse(node->next);
node1->next = node;
node->next = NULL;
return node;
}

/* Function to print linked list */
void print()
{
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}

void push(int data)
{
Node* temp = new Node(data);
}
};

/* Driver program to test above function*/
int main()
{
ll.push(20);
ll.push(4);
ll.push(15);
ll.push(85);

ll.print();

cout << "\nReversed Linked list \n";
ll.print();
return 0;
}
```

Implementation in Python

```# Recursive Python3 program to reverse
import math

class Node:
def __init__(self, data):
self.data = data
self.next = None

# Function to reverse the linked list
def reverse(node):
if (node == None):
return node

if (node.next == None):
return node

node1 = reverse(node.next)
node.next.next = node
node.next = None
return node1

# Function to print linked list
def printList():
while (temp != None) :
print(temp.data, end = " ")
temp = temp.next

new_node = Node(new_data)
new_node.data = new_data

# Driver Code
if __name__=='__main__':

printList()

printList()

```

### Time & Space Complexity Analysis

Recursive

Time Complexity = O(n), where n is the length of the Linked List

Space Complexity = O(n), for recursion stack space.

Iterative

Time Complexity = O(n), where n is the length of the Linked List
Space Complexity = O(1)

With this article at Logicmojo, you must have the complete idea of analyzing Reversing a Linked List

Good Luck & Happy Learning!!