This blog post will help your to learn, How to reverse Linked List using Python.
Input: Before reverse operation on Linked List 1->2->3->4->NULL Output: After Reverse operation Linked list will look like, 4->3->2->1->NULL
So to reverse a Linked List, we have to create a three points
How to create Node in SIngly Linked List using python, You can read out here in few words https://freshlybuilt.com/question/how-to-create-node-for-linked-list-using-python/
Algorithm for Reverse a Linked List
- Initialize three pointers prev as None, curr as head and next as None
- Iterate through the linked list.
- In a Loop follow the bellow steps.
- Before changing the next of current store next node i.e next = current.next
- Now change the next of current, This is a point where actual reversing happens i.e current.next = prev
- Move the prev and current one step forward i.e prev = current, current = next
Reverse a Linked List – Python Code
# Structure for node class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to reverse the linked 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 # Function to insert a new node at the beginning # Function to push data at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Function to print the linked LinkedList def printList(self): temp = self.head while(temp): print(temp.data) temp = temp.next linked_list = LinkedList() linked_list.push(1) linked_list.push(2) linked_list.push(3) linked_list.push(4) print("Given Linked List will look like ") linked_list.printList() linked_list.reverse() print("After reverse function, Reversed Linked List will look like") linked_list.printList()
Given Linked List will look like 1 2 3 4 After reverse function, Reversed Linked List will look like 4 3 2 1
- Time Complexity: O(n)
- Space Complexity: O(1)
It is one of the simplest method to reverse a linked list. What are your views about the recursive method for reversing a linked list. Do you think it is better than this one, Comment it out in comment section. Let’s have good discussion.