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.**

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; node->next = (*head_ref); (*head_ref) = node; } // Function to reverse the list void reverse(struct node **head_ref) { struct node *temp = NULL; struct node *prev = NULL; struct node *current = (*head_ref); while(current != NULL) { temp = current->next; current->next = prev; prev = current; current = temp; } (*head_ref) = prev; } // To check our program void printnodes(struct node *head) { while(head != NULL) { cout<<head->data<<" "; head = head->next; } } // Driver function int main() { struct node *head = NULL; push(&head, 0); push(&head, 1); push(&head, 8); push(&head, 0); push(&head, 4); push(&head, 10); cout << "Linked List Before Reversing" << endl; printnodes(head); reverse(&head); cout << endl; cout << "Linked List After Reversing"<<endl; printnodes(head); return 0; }

**Implementation in Python**

class Node: def __init__(self, val): self.val = val self.next = None def display(head): ptr = head while ptr: print(ptr.val, end = '->') ptr = ptr.next print('X') def reverse_list(head): if not head: return head prev, curr = None, head while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt head = prev return head if __name__=='__main__': head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) head.next.next.next.next.next = Node(6) display(head) head = (reverse_list(head)) display(head)

**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:

head.next.next = head

head.next = NULL

Return the head pointer of the reversed list i.e. return restReversedPart.

**Implementation in C++**

// Recursive C++ program to reverse // a linked list #include <iostream> using namespace std; /* Link list node */ struct Node { int data; struct Node* next; Node(int data) { this->data = data; next = NULL; } }; struct LinkedList { Node* head; LinkedList() { head = NULL; } /* Function to reverse the linked list */ Node* reverse(Node* node) { if (node == NULL) return NULL; if (node->next == NULL) { head = node; return node; } Node* node1 = reverse(node->next); node1->next = node; node->next = NULL; return node; } /* Function to print linked list */ void print() { struct Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } } void push(int data) { Node* temp = new Node(data); temp->next = head; head = temp; } }; /* Driver program to test above function*/ int main() { /* Start with the empty list */ LinkedList ll; ll.push(20); ll.push(4); ll.push(15); ll.push(85); cout << "Given linked list\n"; ll.print(); ll.reverse(ll.head); cout << "\nReversed Linked list \n"; ll.print(); return 0; }

**Implementation in Python**

# Recursive Python3 program to reverse # a linked list import math # Link list node class Node: def __init__(self, data): self.data = data self.next = None def LinkedList(): head = 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(): temp = head while (temp != None) : print(temp.data, end = " ") temp = temp.next def push(head_ref, new_data): new_node = Node(new_data) new_node.data = new_data new_node.next = head_ref head_ref = new_node return head_ref # Driver Code if __name__=='__main__': # Start with the empty list head = LinkedList() head = push(head, 20) head = push(head, 4) head = push(head, 15) head = push(head, 85) print("Given linked list") printList() head = reverse(head) print("\nReversed Linked list") printList()

**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!!**