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;
    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()

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

© 2023 Logicmojo. ALL RIGHTS RESERVED