Reversing a Linked List
We are given a singly linked list, and our task is to reverse the linked list by changing the links between the nodes.
Input:

Output:

Explanation
Here as you can see the list has been reversed.
Now 4->3, 3->2, 2->1.
Now 4 has become the head of the list as it is the starting node of this linked list after performing the reversal action.
Here the only change we can observe is the change in the links. So we have to think of an approach that can change the links between the nodes.
Let’s move to our different approaches to solving this problem.
Recommended: Do try to attempt the Problem yourself before moving on to the solution.
Approach1: Iterative
Algorithm
- Create two nodes-> current and next.
- Initially, current(node) will point to the first element(head), and prev will point to null.
- Store the next the current element in next.
- Traverse through the list till the current become null.
- In the end, the prev will be our head.

The current element will now point to that element stored in the 'prev' variable.





Code
class Node:
# Constructor
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# head function
def __init__(self):
self.head = None
# To reverse the list
def reverse(self):
prev = None
current = self.head
while(current is not None):
next = current.next
current.next = prev
prev = current
current = next
self.head = prev
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# To print the list
def printL(self):
temp = self.head
while(temp):
print temp.data,
temp = temp.next
# Main function
llist = LinkedList()
llist.push(1)
llist.push(2)
llist.push(3)
llist.push(4)
print "Given Linked List"
llist.printL()
llist.reverse()
print "\nReversed Linked List"
llist.printL()

You can also try this code with Online Python Compiler
Run Code
Output
Given Linked list
1 2 3 4
Reversed linked list
4 3 2 1
Time Complexity - O(n).
Space Complexity - O(1).
Approach2: Recursive
Algorithm
- when the curr node is the last node starts with it and also runs after the previous curr.
- Save the following curr to next.
- Next, create from the current point to the previous point.
- Repeat with curr as curr and curr as prev.

Pic referenced from prepbytes.
Code
class Node:
# Constructor
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# head function
def __init__(self):
self.head = None
def reverse_Util(self, curr, prev):
# If last node mark it head
if curr.next is None:
self.head = curr
curr.next = prev
return
# Save curr.next node for recursive call
next = curr.next
# update next
curr.next = prev
self.reverse_Util(next, curr)
# This function calls reverse_Util()
# with previous as Null
def reverse(self):
if self.head is None:
return
self.reverse_Util(self.head, None)
# To insert the new node at the beginningof the list
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# To print the list
def printL(self):
temp = self.head
while(temp):
print temp.data,
temp = temp.next
# Main function
llist = LinkedList()
llist.push(1)
llist.push(2)
llist.push(3)
llist.push(4)
print "Given linked list"
llist.printL()
llist.reverse()
print "\nReverse linked list"
llist.printL()

You can also try this code with Online Python Compiler
Run Code
Output
Given linked list
4 3 2 1
Reverse linked list
1 2 3 4
Time Complexity: O(n)
Space Complexity: O(n)
To read about Fibonacci Series in Python click here.
Must Read C Program to Reverse a Number
Frequently Asked Questions
What do you mean by reverse a linked list?
You will be given a linked list, and you have to print the reverse linked list by changing the links between the nodes.
What are the approaches we used to find the reverse of a linked list?
We have used two efficient approaches to solve this problem, i.e., Iterative and Recursive.
Conclusion
To print the reverse of a linked list is one of the most straightforward problems of a linked list topic. We have seen the implementation of a singly linked list and two approaches to finding the reverse of the list in Python language.
If you want to prepare for interviews, you can visit Coding Ninjas Studio and brush up on your skills for top product-based companies.
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Keep Coding!!!